깊이 우선 탐색은 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
깊이 우선 탐색은 제한 조건에 따라 일정 부분을 제외하고 전체직인 그래프를 탐색할 때 사용한다.
예시를 들어 dfs에 대해 더욱 자세히 이해해보자.
문제
한 반에 7명의 학생이 존재한다.
해당 반에서 다른 반과 줄다리기 시합을 진행하는데, 서로 싫어하는 학생끼리 이웃하게 세우면, 경기력이 저하된다.
어떻게 하면 정상적인 경기력으로 줄다리기를 할 수 있게 학생들을 일렬로 세울 수 있을까?
정상적인 경기력이 나오도록 반 학생들을 세울 수 있는 모든 방법의 수를 구하시오.
입력 예시
int N = 7; // 반의 총 학생수
int[] arr = new int[][]{{1, 3}, {5, 7}, {4, 2}}; // 서로 싫어하는 학생들의 배열
어떻게 해야 그래프를 탐색할 때 최소한으로 탐색하면서 세울 수 있는 모든 방법의 수를 구할 수 있을까?
가장 간단한 방법으로 생각한다면, 모든 방법의 수를 찾은 후에 세운 방법을 하나씩 싫어하는 학생들의 배열과 비교하는 방법이 존재하지만, 학생수가 많아지거나, 싫어하는 학생들의 배열이 길어지면 시간초과가 발생할 확률이 높다.
다른 방법으로 생각할 수 있는게 깊이 우선 탐색으로 노드들을 탐색하면서, 이전 노드와 현재노드를 비교해, 두 노드가 싫어하는 학생들의 배열에 존재하는지 확인하는 것이다.
이렇게 하면 해당 가지가 싫어하는 학생들의 배열을 포함하는지 계속 확인하기 때문에, 해당 가지의 탐색을 계속 진행해도 될지, 아니면 계속 탐색해야 할지를 알 수 있다.
위의 생각을 코드로 구현해보자.
public int solution(int[][] fight) {
answer = 0;
graph = new int[8][8];
pm = new int[8];
visited = new int[8];
for (int[] ints : fight) {
int x = ints[0];
int y = ints[1];
graph[x][y] = 1;
graph[y][x] = 1;
}
dfs(0);
return answer;
}-
노드간 연결관계를 알고 싶을때는 그래프를 인접리스트 방식으로 구현하는 것보다 인접행렬 방식하는 것이 효율적이기에, 인접행렬 방식으로 구현했다.
-
그래프는 x에서 y로 이동할 수 없는 경우 1, 이동할 수 있는 경우 0으로 값을 입력했다.
(서로 싫어하는 학생들을 값을 1로 지정해 그래프를 탐색하면서 1이 나오면 다른 가지로 넘어가서 탐색하도록 만들었다.)
public void dfs(int L) {
if (L == 7) {
answer++;
} else {
for (int i = 1; i <= 7; i++) {
if (L >= 1) {
if (graph[pm[L]][i] == 1) {
continue;
}
}
if (visited[i] == 0) {
visited[i] = 1;
pm[L + 1] = i;
dfs(L + 1);
visited[i] = 0;
}
}
}
}-
깊이 탐색을 하면서 깊이가 7이 되는 경우 학생들을 1열로 세우는 경우가 생긴 것이므로 answer에 1을 더한다.
-
그래프가 1번 노드부터 시작하기 때문에, for문도 1부터 돈다.
-
L이 1보다 큰 경우, 일렬로 세운 줄에 2명 이상의 학생이 존재하므로, 이전 노드와 현재 노드가 싫어하는 학생들의 배열에 속하는 지 확인하고, 속하면 다음 가지로 이동하기 위해 continue를 실행한다.
-
속하지 않는다면, 해당 노드를 다시 방문하지 않기 위해 visited 배열로 체크해주고, 현재 방문한 노드를 pm 배열에 저장해둔다.
결론
이렇게 제한 조건에 따라 더 깊은 깊이를 탐색할지 말지를 결정하며, 그래프를 탐색하면 할때 효율적인 탐색이 가능해진다.
