반응형 백트래킹1 [알고리즘] 백준. #15649 N과M(1) 이번 문제는 "백트래킹(backtracking)"에 관한 문제라는데, 솔직히 백트래킹이 뭔지 몰랐다. *한국어로는 '퇴각 검색'이라고 한다. 어감에서 느껴지는 의미로는 뒤로 추적해가면서 뭔갈 풀어내는 거 같긴 한데,, 찾아보니 문제를 푸는 모든 경우의 수를 고려하되, check point를 잡아 놔서 풀다가 막히면 check point로 돌아가 다른 풀이를 모색하는 것 같다. 모든 경우의 수를 하나의 트리 형태로 구현해 놓고, 트리를 깊이 우선 탐색(dfs)을 하다가 막히면 부모 노드로 가서 다시 탐색을 하는 식인 것 같다. 여기서 부모노드가 일종의 check point 역할을 한다. 주로 재귀, 큐, 스택을 이용해서 푼다고 한다. 다시 check point로 돌아가기 위해 재귀적인 방식이나 스택을 쓰는.. 2020. 6. 4. 반응형 이전 1 다음
