깊이우선탐색(DFS;Depth-First Search)

DFS 란?

깊이우선탐색(DFS;Depth-First Search) 알고리즘은 그래프나 트리구조에서 깊이를 우선으로 탐색하는 알고리즘이다.

즉 한 경로를 끝까지 다 탐색한 후에 다음 경로로 넘어가 탐색을 이어간다.

주로 스택(Stack)이나 재귀함수를 사용하여 구현하고, 더이상 탐색할 노드가 없으면 이전 분기점으로 돌아간다(=백트래킹).

 

 

DFS의 동작 방식

0. 탐색이 필요한 노드를 저장할 스택과 방문 처리를 위한 visited 변수가 필요하다.

1. 시작노드를 스택에 넣는다

2. 스택이 비어있지 않다면 아래 내용을 반복한다.

• 스택 최상단 노드를 현재 노드로 지정한다.
• 현재 노드에 인접한 미방문 노드가 있으면 그 노드를 스택에 넣고 방문처리한다.
• 인접한 미방문 노드가 없으면 스택에서 노드를 꺼낸다.

 

 

 

BFS 구현 예제

[백준/Silver II] 알고리즘 수업 - 깊이 우선 탐색 1 - 24479

위 링크의 문제로 예시를 살펴보자. 문제에서 제시하는 입출력 예시의 그래프는 아래와 같다.

시작 노드 1을 스택에 담고, 방문처리하면

다음 탐색 노드를 저장하는 stack과 방문 여부를 표시하는 visited는 아래와 같다.

 

stack

1

 

visited

node	1	2	3	4
visited	true	false	false	false

 

 

1번 노드에서 인접한 2번 노드를 스택에 담고, 방문 처리한다.

 

stack

2

1

 

visited

node	1	2	3	4
visited	ture	true	false	false

 

2번 노드에서 인접한 3번 노드를 스택에 담고, 방문 처리한다.

stack

3

2

1

 

visited

node	1	2	3	4
visited	ture	true	true	false

 

 

3번 노드에서 인접한 4번 노드를 스택에 담고, 방문 처리한다.

stack

4

3

2

1

 

visited

node	1	2	3	4
visited	ture	true	true	true

 

 

4번 노드에서 인접한 노드가 없으므로 스택에서 삭제한다.

stack

3

2

1

 

visited

node	1	2	3	4
visited	ture	true	true	true

 

이후 스택에 저장된 노드 3, 2, 1에 대해 방문 가능한 인접한 노드가 없으므로 삭제된다.

 

아래는 해당 문제를 Java 코드로 구현한 예시이다.

import java.io.*;
import java.util.*;

public class Solution {

    int[] dfs(int root, ArrayList<Integer>[] map){
        boolean[] visited = new boolean[map.length]; // 노드(index)방문 여부
        int[] order = new int[map.length]; // 노드(index) 순회 순서 저장
        
        Stack<Integer> path = new Stack<>(); // 다음 방문 노드 Stack
        path.push(root); // Stack에 시작 노드 삽입

        int cur, next;
        int cnt = 1; // 순서
        while(!path.isEmpty()){ // path에 저장된 경로를 다 돌아야 함.
            cur = path.pop();
            if(visited[cur]) continue; // 이미 방문한 노드면 continue
            order[cur] = cnt++; // 방문 순서 저장
            visited[cur] = true; // 방문 여부 표시
            
            // 인접 노드들 중 방문한 적 없고, path에 없는 노드들을 path에 저장
            if(map[cur] == null) continue; // 인접 노드 없으면 continue;
            for(int i = map[cur].size() - 1; i >= 0; i--){
                next = map[cur].get(i);
                if(!visited[next]){
                    path.push(next);
                }
            }
        }
        return order;
    }
    ...
}

 

 

❗️ 재귀 방식의 경우를 보고싶으면 아래에서 확인할 수 있다.

[백준/Silver ||] 알고리즘 수업 - 깊이 우선 탐색 1 - 24479 (재귀로 해결)

[백준/Silver II] 알고리즘 수업 - 깊이 우선 탐색 1 - 24479