[PS][완전탐색][DFS] Chapter 1
완전탐색의 두 번째 알고리즘 DFS 문제를 풀어보겠습니다.
친구
문제의 정답은 여기에서 확인할 수 있습니다.
딱 보면 bfs 문제이지만 dfs로 풀기 위해서는 방문했던 노드도 다시 방문해야합니다. 아래와 같이 싸이클이 있는 경우 5에서 3으로 방문하고, 3에서 4로 방문하면 싸이클은 모두 커버할 수 있습니다. 하지만 5 - 4 - 6으로 이어지는 6은 방문하지 못하기 때문에 방문했던 노드라도 일단 방문하고 dfs를 한 번 더 진행하도록 해야합니다. 가지치기의 경우는 n자리 k진수에서 배웠던 형식을 적용합니다.
7
NYNNNNN
YNYNNNN
NYNYNNN
NNYNYYN
NNNYNYY
NNNYYNN
NNNNYNN
트리
문제의 정답은 여기에서 확인할 수 있습니다.
문제는 간단한데 고려할 사항을 생각해보는 연습이 필요합니다.
- root를 지울 수 있다.
- root가 여러 개일 수 있다.
- root의 노드번호가 0이 아닐 수 있다.
- 문제의 조건에 따라서 한 노드의 부모는 반드시 하나의 노드이다.
- 따라서 지우고자하는 노드에서 dfs()를 진행해서 자식노드를 모두 방문할 수도 있고, 지울 노드만 방문했다고 처리해서 dfs가 진행되지 않도록 할 수도 있다.
빙산
문제의 정답은 여기에서 확인할 수 있습니다.
- 문제의 조건만 잘 지키면 되는 문제네요.
숫자고르기
문제의 정답은 여기에서 확인할 수 있습니다.
문제를 보면 주어지는 입력을 인접리스트로 바꾸어서 그래프로 생각할 수 있습니다. 이 때 싸이클을 이루는 노드들을 하나의 그룹으로 묶고, 모든 그룹을 고르면 됩니다. 싸이클이 존재하는지 판단할 때는 dfs()인자에 시작하는 노드와 현재 보고 있는 노드를 param으로 전달해서 해결합니다.
만약 현재 노드에서 연결되는 다음 노드가 이미 방문한 노드일 때, ‘다음 노드’가 start와 같으면 cycle이 됩니다.
(1 -> 2 -> 3 -> 1의 싸이클에 대해서 3에서의 다음 노드는 1이고, 시작 노드가 1이므로 싸이클입니다.)