[백준] 15649 - N과 M
문제
문제 설명 및 풀이
백트래킹의 전형적인 문제 중 하나이다. 백트래킹이란 쉽게 이야기하자면 말 그대로 (방금 왔던 길을) 되짚어가는 것을 말한다. 조금 어렵게 설명한다면, 현재 상태에서 가능한 모든 후보를 살펴보며 탐색하는 알고리즘을 말한다.
이 문제에서는 DFS라는 탐색법을 사용하면 쉽게 풀 수 있다. 기본적으로 백트래킹은 DFS, BFS를 굉장히 많이 사용한다. 위 알고리즘들은 다음에 정리하여 포스팅하도록 하겠다.
처음 이 문제를 풀 때, 단번에 풀이를 알기란 쉽지가 않다. 고도의 구현력이 필요하며, 코드를 봐도 이해하는 데 시간이 오래 걸릴지도 모른다. 그런 사람들은 그림을 그려가며 천천히 재귀 함수를 공부하길 바란다.
아래의 코드 형태를 잘 외워두길 바란다. 처음에는 외우고 이후 비슷한 유형의 문제들을 풀다 보면 서서히 감이 올 것이다. 필자도 처음 이런 풀이를 보았을 때 충격을 받았던 기억이 난다. 재귀는 코딩이 간단하면서도 굉장히 강력한 도구임을 알게 된다. 구현은 다음과 같다. 재귀하면서 이미 방문한 노드는 다음 노드를 탐색해야 하는데, 이를 검사하기 위해 visited라는 boolean 배열을 만들고, 탐색 과정에서 정답을 입력해 둘 ans 배열을 만들어 둔다. cnt를 증가 시켜 M과 같아지면 더 이상 함수를 호출하지 않고 정답 배열을 출력해 주고 return 해준다. 재귀에서 base condition을 설정하는 것은 매우 중요하다. 자칫 잘못하면 무한 루프에 빠질 수 있기 때문이다. 같지 않다면, 탐색하면서 이미 탐색했다면 넘어가고 그렇지 않다면 ans 배열에 추가하며 재귀가 깊어지는 것을 알 수 있다.
더 자세한 설명을 원하는 사람들은 아래 사이트를 방문하길 바란다. 다른 사람들의 코드 리뷰를 하던 중 알게 된 분인데, BaaaaaaaarkingDog님의 글이다. 정말 설명을 기가 막히게 잘한 글이다.
코드
TMI
혹여나 브루트 포스와 백트래킹을 동일시할까 봐(둘 다 DFS, BFS 등으로 풀 수 있어서) 글을 남긴다. 백트래킹이 현재 상태에서 가능한 모든 후보를 살펴본다고 하여 브루트 포스의
"가능한 모든 경우의 수를 찾는다"와 동일하게 생각하면 안 된다. 중요한 키워드는현재 상태이다. 백트래킹은 DFS, BFS를 기반으로 하는 일종의 트리 탐색 알고리즘이라고 볼 수 있다. 어떤 노드의 유망성을 따져보고 유망하지 않으면 그 노드의 부모 노드로 돌아간 후 다른 자손의 노드를 탐색한다. 즉, 유망성 점검을 통해 브루트 포스와 달리 가지가 형성되어 1차원적으로 모든 수를 따져보는 것은 아니다. 조건을 충족한다면(유망하다면), 계속해서 부분집합 해를 만들어나가고, 그렇지 않다면 한 단계 뒤로 가서 다른 해를 찾는 것이 백트래킹이다.
