Hee's Story

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀기 전 생각 DFS를 사용해서 풀어야겠다. 무한루프에 빠지지 않기 위해 방문한 노드들을 확인한다. 이 때, 다음에 돌 때를 위해 방문한 노드들을 다시 false로 만들어준다. 예를 들어 아래의 경우 노드 2를 방문하고 난 후 노드 3으로 갈 때 방문표시를 false로 하지 않으면 1->2->3->4으로 끝나버린..

Backtracking (백 트래킹) 모든 경우의 수를 전부 고려하는 알고리즘이다. 즉, 조합 알고리즘 문제에 대해 어떤 조건을 만족할 때 모든 가능한 해를 나열한 것이다. 일종의 트리 탐색 알고리즘으로 DFS, BFS 등의 방식을 사용한다. DFS 모든 경우의 수를 고려해야 하는 문제일 때 주로 사용한다. 하지만 트리의 깊이가 무한대가 될 때는 절대 사용하면 안된다. (무한루프에 빠짐) -> 이 때, 중복검사를 따로 해야 함 BFS 최단거리를 구할 때 주로 사용한다. Backtraking의 대표적인 예제로 N-Queen이 있다.