[백준 알고리즘][DFS][백트래킹] 6603번 로또

문제 정의

1~49의 숫자 중에서 k(k>6)개의 숫자를 골라 집합을 만들고, 그 집합에서 6개의 숫자조합을 만드는 모든 방법을 출력해야 한다. 

문제 출처: 백준 온라인 저지 (https://www.acmicpc.net/problem/6603)

문제 풀이

k개의 숫자 중에서 6개의 숫자를 고르는 모든 방법을 구하고, 그 방법에 해당하는 숫자를 출력해야 한다. 사실 이 문제는 다른 문제를 풀던 와중에 m개 중에서 n개를 고르기와 같은 경우를 어떻게 찾아야 할지 해결을 하지 못해 찾아보다가 풀게 된 문제다. 이러한 문제를 풀 때는 DFS에서 백트래킹을 응용해서 풀어야 한다. 주어진 집합 k개 숫자는 서로 다 이어져 있는 그래프라고 생각을 하고 DFS를 하다가 6개가 되면 하나의 방법을 찾은 것이고, 출력한다. 그리고 백트래킹을 통해서 방문하지 않은 번호를 계속해서 탐색한다. 이런 식으로 백트래킹을 통해 방문하지 않은 번호가 없을 때는 모든 경우를 다 출력한 것이다. 이렇게 DFS를 하며 백트래킹을 응용시키면 따로 모든 케이스에 대해 저장을 해둘 필요도 없고 간단하게 탐색을 할 수 있다. 앞으로 문제를 풀 때 m개 중에서 n개를 골라야 하는 경우는 DFS+백트래킹을 떠올려야 한다! 

코드를 짜고 있는데 무한루프에 걸렸다. 백트래킹을 잘못 짠 것 같다. 이전에 개념 정리할 때도 백트래킹 문제는 거의 틀렸었는데 이번에도 백트래킹의 개념을 제대로 적용하지 못한 것 같다. DFS를 수행하며 스택에 쌓으며 탐색을 하다가, 숫자가 6개 되는 순간 출력을 하는 부분까지는 맞는 것 같다. 그다음 visited 배열을 이용해서 방문하지 않은 다른 번호를 방문해가며 6개의 조합을 계속 만들어야 하는데 이 부분을 어떻게 고쳐야 할지 잘 떠오르지 않는다.

결국 정답인 코드를 보고 참고해서 고쳐봤다. 너무 오랜만에 DFS를 짜느라 BFS로 짜고 있어서 이상했던 거였다. 항상 헷갈린다. 입력값 자체가 오름차순으로 들어오기 때문에 탐색할 때 백트래킹 후 다음 노드로 계속 이어나갈 테니 visited 배열 없이도 문제를 해결할 수 있다. DFS는 재귀로 쉽게 짤 수 있고, 기본적인 문제에서는 따로 스택이 필요 없다는 걸 까먹지 않아야겠다.