[알고리즘] 그래프 탐색 알고리즘 - DFS, BFS

(학교 수업 자료를 참고하여 작성하였습니다.)

 

DFS, BFS는 탐색 알고리즘으로 브루트포스에 포함된다. 주로 그래프와 트리를 순회할 때 사용되고, 탐색 방법과 목적에는 약간의 차이가 있다. 그치만 코딩테스트 문제들에서 DFS, BFS를 따지지 않고 탐색만 하는 것으로 해결되는 경우도 많다고 한다. 

• 그래프: 연결되어 있는 객체 간의 관계를 표현하는 자료구조
• 트리: 그래프의 한 종류로, 사이클이 없는 N개 노드, (N-1)개 간선을 가진 연결된 그래프

그래프는 인접 행렬(O(N^2)), 인접 리스트(O(N+E)) 형태로 구현한다. 

https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

깊이 우선 탐색, DFS

• DFS: Depth-First Search의 약자로 깊이 우선 탐색을 말한다
• 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색한다
  = 방문하지 않은 인접 노드가 없을 때까지 탐색 진행
• 되돌아가기 위해서는 스택이 필요
  ⇒ 주로 재귀함수를 호출하여 묵시적으로 스택 이용

- 적용

• 시작 노드로부터 먼 solution이 있을 때 더 suitable
• 경로가 존재하는지 여부를 파악하는 문제
• 최단 경로를 찾는 것은 보장하지 않음
• 지나온 경로의 특징을 저장하고 추적하는 문제에 적합
• ex. 특정 노드 포함 경로 찾기, 가중치 합이 특정 조건을 만족하는 경로 찾기

- 탐색 방법

 

1. 시작 노드를 호출하여 방문 배열에 표시한다.

2. 그의 방문하지 않은 인접 노드를 호출하는 것으로 반복한다.

3. 내부 함수가 종료되면 호출한 곳으로 다시 돌아간다.

 

- 코드 

구현 시 인접 행렬 혹은 인접 리스트(ex. ArrayList<ArrayList<Integer>> A 배열)와 방문 배열(ex. boolean visited 배열)을 필요로 한다.

static void dfs(int node) {
    visited[node] = true; // 해당 노드를 방문했다고 표시
    for(int i: A[node]) { // 해당 노드의 인접 노드 탐색
    	if(!visited[i]) { // 방문하지 않은 인접 노드가 있다면
            dfs(i); // 재귀 함수 호출로 깊이 탐색 진행
        }
    }
}

너비 우선 탐색, BFS

• BFS: Breadth-First Seach의 약자로 너비 우선 탐색을 말한다
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 큐를 사용하여 구현
  - 큐 구현 시 LinkedList를 사용하는 것보다 ArrayDeque를 사용하는 게 성능상 우수하다

* ArrayDeque

"This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. " (cf. https://docs.oracle.com/javase/8/docs/api/)

Java Platform SE 8

 

- 적용

• 시작 노드로부터 인접한 정점들을 먼저 탐색할 때 더 suitable
• 출발지로부터 인접한 모든 가능한 경로 탐색, 한 층씩 너비를 늘려가며 목적지에 도달하는 경로 찾을 수 있음
• 이분 그래프, 최단 경로
• 모든 경로의 깊이(depth)나 이동 횟수(count) 계산하고 비교
• ex. 미로에서의 최단 경로 구하기, 특정 거리의 노드 찾기

- 탐색 방법

 

0. 큐를 생성한다. 

1. 시작 노드를 큐에 삽입하고 방문 배열에 표시한다.

2. 큐가 빌 때까지 요소를 꺼낸다.

    2.1. 큐의 맨앞 요소를 꺼낸 후, 그의 방문하지 않은 인접 노드가 있다면 큐에 삽입한다. (큐에 이미 삽입된 노드는 추가하지 않는다.)

    2.2. 방문 배열에 해당 인접 노드를 표시한다. 

 

 

- 코드 

구현 시 인접 행렬 혹은 인접 리스트(ex. ArrayList<ArrayList<Integer>> A 배열)와 방문 배열(ex. boolean visited 배열)을 필요로 한다.

(cf. 이중 배열 https://stackoverflow.com/questions/24796273/incompatible-types-list-of-list-and-arraylist-of-arraylist)

static void bfs(int node) {
    Queue<Integer> queue = new ArrayDeque<>(); // ArrayDeque로 구현
    queue.offer(node); // 시작 노드 삽입
    visited[node] = true; // 방문 배열에 표시
	
    while(!queue.isEmpty()) { // 큐가 빌 때까지 진행
    	int num = queue.poll(); // 맨 앞 요소 꺼내어
       	for(int i: A[num]) { // 해당 노드의 인접 노드 탐색
            if(!visited[i]) { // 방문하지 않은 노드가 있다면
                queue.offer(node); // 큐에 삽입함
                visited[node] = true;
            }
    	}
    }
}

 

cf. https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

Difference between BFS and DFS - GeeksforGeeks

https://www.acmicpc.net/source/77026419

https://www.acmicpc.net/source/56402164