[알고리즘] 그래프 (Graph) - 2. 그래프 탐색

코딩 테스트 합격자되기 chap 11 그래프를 바탕으로 작성하였습니다.

 

그래프 탐색

자료구조에서 어떤 순서와 방식으로 데이터를 탐색할 지 고민해야 한다.
그래프에서 경로를 찾는다고 할 때 경로를 찾는 방법은 크게 2가지가 있다.

• 더 이상 탐색할 노드가 없을 때까지 가본다. 그러다 더 이상 탐색할 노드가 없으면 최근에 방문했던 노드로 되돌아간 다음 가지 않은 노드를 방문한다. (깊이 우선 탐색)
• 현재 위치에서 가장 가까운 노드부터 모두 방문하고 다음 노드로 넘어간다. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문한다. (너비 우선 탐색)

 

📌 깊이 우선 탐색 (DFS, depth-first search)

1단계
노드 A에서 노드 D까지 차례대로 방문한다. 노드 D까지 방문하면 더 방문할 곳이 없다.

2단계
노드 D에서 B로 돌아온다. 여기서 다시 갈 수 있는 곳까지 간다. 즉, 노드 Eㄷ까지 방문한다.

3단계
다시 노드 E → B → A 순으로 돌아온다. 그 다음 끝까지, 다시 노드 C까지 간다.
A → B → D → E → C 순서로 모든 노드를 방문

 

📌 너비 우선 탐색 (BFS, Breadth-first search)

1단계
노드 A에서 가장 가까운 노드 B, C 방문

2단계
노드 B에서 가장 가까운 노드 D, E를 방문한다.
A→ B → C → D → E로 모든 노드를 방문

 

 

깊이 우선 탐색 (DFS)

시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하며 차례로 방문한다.
최대 깊이 노드까지 방문한 다음 이전에 방문한 노드를 거슬러 올라가며 해당 노드와 연결된 노드 중 방문하지 않은 노드로 다시 최대 깊이까지 차례대로 방문한다.

탐색을 하려면 일단 시작 노드를 정하고, 스택에 시작 노드를 push한다.
스택에 있는 노드는 아직 방문하지 않았지만 방문할 예정인 노드이다.
시작 노드를 push 했으면, 다음 과정을 반복한다.

1. 스택이 비었는지 확인
   스택이 비어있다 == 방문할 수 있는 모든 노드를 방문
   → 스택이 비어있으면 탐색 종료
2. 스택에서 노드 pop
   pop한 원소는 최근에 스택에 push한 노드이다.
3. pop한 노드의 방문 여부 확인
   아직 방문하지 않았다면 노드를 방문 처리 한다.
4. 방문한 노드의 인접한 모든 노드를 확인
   그리고 그 중 아직 방문하지 않은 노드를 스택에 push
   stack은 FILO 구조이므로 방문 순서를 오름차순으로 고려한다면 역순으로 노드를 push 해야 한다.

이 과정을 코드로 구현할 때 다음 3가지를 고려해야 한다.

1. 탐색할 노드가 없을 때까지 간선을 타고 내려갈 수 있어야 한다.
2. 가장 최근에 방문한 노드를 알아햐 한다.
3. 이미 방문한 노드인지 확인할 수 있어야 한다.

dfs의 핵심은 가장 깊은 노드까지 방문한 후 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음 해당 노드에서 방문할 노드가 있는지 확인하는 것이다.

탐색의 역방향으로 되돌아가는 것을 백트래킹(Back Tracking)이라고 한다.
스택은 최근에 push한 노드를 pop할 수 있으므로 특정 노드를 방문하기 전에 최근 방문 노드를 pop 연산으로 쉽게 확인할 수 있다.
다음은 이런 스택의 특성을 활용하여 백트래킹 동작을 쉽게 구현한 것이다.

 

📌  스택을 활용한 깊이 우선 탐색

선입후출의 특성을 가진 스택으로 가장 최근에 방문한 노드를 확인할 수 있다.

1단계
스택에 방문 예정인 노드 push
시작 노드는 당연히 방문해야 할 노드 : 1을 스택에 넣는다.
(스택에 푸시한 노드 : 파란색, 방문한 노드 : 회색)
1은 아직 방문하지 않았고, 방문할 예정

 

2단계
1을 pop 한 후 1이 방문한 상태인지 확인
1은 아직 방문하지 않았으므로 방문처리 (회색으로 칠함)
방문 처리 후 1과 인접하면서 아직 방문하지 않은 노드 4,5를 5 → 4 순서로 push 하여 이후 4 → 5 순서로 방문 처리할 수 있게 한다.

* 이러한 방식처럼 스택에 역순으로 push 하면 의도한대로 방문 처리를 할 수 있다.

 

3단계
같은 방식으로 pop, push 진행
스택에서 4를 pop한 다음, 4가 방문한 상태인지 확인
4는 아직 방문하지 않았으므로 방문 처리
그런 다음, 4와 인접한 2,3을 3 → 2 순서로 push

 

이런식으로 방문하지 않은 노드를 스택에 넣고
pop 한 뒤 방문 처리하고 다시 인접한 방문하지 않는 노드를 스택에 넣는 것을 스택이 빌 때까지 반복한다.

 

📌  재귀 함수를 활용한 깊이 우선 탐색

스택을 직접 사용하지 않고도 재귀 함수를 활용하여 깊이 우선 탐색을 구현할 수 있다.
재귀 함수를 호출할 때마다 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 dfs에 활용할 수 있다.
호출할 함수를 dfs( )로 선언하고, dfs(n)을 호출하면 다음 동작을 하도록 구현했다고 가정한다.

* 여기서 인접한 노드를 방문할 때 숫자가 낮은 노드부터 탐색하는 방식으로 설명

* dfs(n) : n번 노드를 방문 처리하고 n번 노드와 인접한 노드 중 아직 방문하지 않은 노드를 탐색

1단계
시작 노드 : 1번 → dfs(1) 호출
dfs(1)이 실행되면 1을 방문처리하고 내부적으로 dfs(4)를 재귀 호출한다.
dfs(1)은 dfs(4)를 호출한 상태이므로 종료되지 않는다.
따라서 스택에 dfs(1)이 쌓인다.

 

2단계
dfs(4)가 실행되므로 4는 방문 처리하며, 내부적으로 dfs(4)는 dfs(2)를 호출한다.
같은 이유로 dfs(4)는 스택에 쌓인다.

 

3단계
dfs(2)를 실행한다. 2를 방문처리하고 dfs(2)는 dfs(3)을 재귀 호출한다.

 

4단계
dfs(3)을 실행한다. 3은 인접 노드가 없으므로 추가로 재귀 호출을 하지 않고 함수를 종료한다.
여기서 처음으로 스택에서 빠져나오는 함수가 생긴다.

 

5단계
스택 특성에 의해 dfs(2)로 돌아가 다음 실행 스텝을 진행한다.
그러나 2는 인접한 노드가 없으므로 다른 재귀 함수를 호출하지 않고 종료된다.

 

6단계
dfs(4)로 돌아가 다음 실행 스탭을 진행한다.
4도 인접 노드가 없어 함수를 종료한다.
2의 다음 노드인 3이 인접하므로 탐색을 시도하지만, 3은 이미 방문한 노드이다.
따라서 변경된 부분 없이 해당 함수가 종료된다.

 

7단계
dfs(1)의 다음 실행 스텝을 진행한다.
1은 5와 인접해 있으므로 dfs(5)를 재귀 호출 한다.

 

8단계
dfs(5)를 실행한다. 5를 방문 처리하고 5와 인접한 노드가 없으므로 dfs(5)를 종료한다.
dfs(1)도 이어서 종료한다.

 

 

너비 우선 탐색 (BFS)

너비 우선 탐색은 시작 노드와 거리가 가장 가까운 노드를 우선으로 하여 방문하는 방식의 알고리즘
이때의 거리는 시작 노드와 목표 노드까지의 차수이다. (간선 가중치의 합이 아님)
탐색을 하려면 시작 노드를 정하고, 큐에 시작 노드를 push 한다.
시작 노드를 큐에 push하면서 방문 처리를 한다.
큐에 있는 노드는 이미 방문처리를 했고, 그 노드와 인접한 노드는 아직 탐색하지 않은 상태라고 보면 된다.

1. 큐가 비었는지 확인한다.
   큐가 비어있다면 방문할 수 있는 모든 노드를 방문했다는 의미 → 탐색 종료
2. 큐에서 노드 pop
3. pop한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드를 큐에 push 하며 방문 처리를 한다.

이 과정을 코드로 구현할 때 다음 두 가지 사항을 고려해야 한다.

1. 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 한다.
2. 이미 방문한 노드인지 확인할 수 있어야 한다.

너비 우선 탐색 방식을 보면 시작 노드부터 인접한 노드를 모두 방문한 후 그 다음 단계의 인접 노드를 방문한다.
즉, 먼저 발견한 노드를 먼저 방문한다.
이러한 특성 때문에 너비 우선 탐색을 할 때에는 큐를 활용한다.

 

📌  큐를 활용한 너비 우선 탐색

1단계
시작 노드 1을 큐에 푸시하고 방문 처리

 

2단계
1을 pop한 후 인접한 4와 5를 확인
아직 방문하지 않았으므로 방문 처리를 하고 4,5 순서로 큐에 푸시

 

3단계
4를 pop한 후 인접한 2와 3을 본다. 아직 방문하지 않았으므로 방문 처리하고 2,3 순서로 큐에 푸시

 

4단계
5를 pop한 후 인접한 1과 4 확인
이미 방문 → 아무 것도 하지 않는다.
큐의 나머지 노드들도 자신과 인접한 노드들을 모두 방문했으므로 아무것도 하지 않고 팝
큐가 비면 탐색을 마무리

 

 

깊이 우선 탐색 vs 넓이 우선 탐색

DFS와 BFS는 모두 탐색 알고리즘으로, 차이가 없어보일 수 있지만 분명한 차이를 보인다.
DFS는 깊게 탐색 후 되돌아오는 특성이 있고,
BFS는 가중치가 없는 그래프에서 최단 경로를 보장한다.

 

📌 깊이 탐색 후 되돌아오는 깊이 우선 탐색

DFS는 가장 깊은 곳을 우선 탐색하고, 더 이상 탐색을 할 수 없으면 백트래킹 하여 최근 방문한 노드부터 다시 탐색을 진행한다는 특징이 있다.
따라서 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나, 그래프의 사이클을 감지해야 하는 경우 활용할 수 있다.
코테에서는 탐색을 해야할 때, 최단 경로를 찾는 문제가 아니면 깊이 우선 탐색을 고려해보는 것이 좋다.

 

📌 최단 경로를 보장하는 너비 우선 탐색

BFS는 찾은 노드가 시작 노드로 부터 최단 경로임을 보장한다.
시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문이다.
너비 우선 탐색은 미로 찾기 문제에서 최단 경로를 찾거나, 네트워크 분석 문제를 풀 때 활용할 수 있다.

 

📌 방문 처리 시점이 다른 이유

방문 처리 시점이 다른 이유는 탐색 방식이 다르기 때문이다.

DFS : 스택에서 pop하면서 방문 처리

• 스택에 다음에 방문할 인접한 노드를 push
• 스택에 push할 노드는 방문 예정인 노드이므로 pop하면서 방문 처리

BFS : 큐에서 push하면서 방문 처리

• 지금 방문할 노드를 push
• 그래야 인접한 노드부터 탐색할 수 있다.

 

 

reference

https://goldenrabbit.co.kr/2023/12/13/%ec%bd%94%eb%94%a9-%ed%85%8c%ec%8a%a4%ed%8a%b8-%ed%95%a9%ea%b2%a9%ec%9e%90-%eb%90%98%ea%b8%b0-%ea%b7%b8%eb%9e%98%ed%94%84-2-%ea%b7%b8%eb%9e%98%ed%94%84-%ed%83%90%ec%83%89/

[코딩 테스트 합격자 되기] 그래프 - 2. 그래프 탐색 - 골든래빗