DFS, BFS 정리 및 활용(백준 11724)

📌문제접근

문제: 백준 11724(연결요소의 개수)
이 문제를 통해 그래프 탐색 알고리즘의 대표적인 두 가지 방법인 DFS와 BFS에 대해 설명하고자 한다.
문제는 3가지 방법으로 해결하였다.

1. DFS - 재귀함수 활용
2. DFS - 스택 활용
3. BFS - 큐 활용

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

시작 노드에서 가능한 깊게 들어간 뒤, 더이상 갈 수 없으면 다시 돌아와 다른 경로를 탐색하는 방식이다.

• 스택이나 재귀함수를 통해 구현
• 어떤 노드를 방문했는지 반드시 검사해야 함
• 모든 경로를 완전 탐색할 때 유리

위의 방법으로 그래프를 탐색하는 것을 깊이우선탐색이라고 한다.
종료 후 방문한 노드를 확인하면 1 -> 2 -> 3 -> 4 -> 6 -> 5 순서가 된다.
6에서 5를 방문할 때에는 4 -> 3 -> 2 순서로 올라가면 인접한 노드가 있는지 탐색한다. 이러한 진행을 백트래킹(backtracking)이라고 한다.

DFS 구현방법 (재귀 기반)

1. 시작노드 방문(visit 표시)
2. 인접한 노드 방문
   2-1. 인접한(방문 가능한) 노드가 없으면 종료. 이전 노드로 돌아감.
   2-2. 인접한(방문 가능한) 노드가 있으면 방문(visit 표시, 재귀 호출)
3. 시작노드로 돌아갈 때까지(또는 스택이 모두 빌 때까지) 2번 단계를 반복
4. visit이 표시되지 않은 정점부터 다시 DFS 진행

📌재귀함수를 이용한 DFS 코드

void DFS(int root){
	visited[root] = true; // (1단계) root노드 방문 기록.
	
    // (2단계)
	for(int i = 0 ; i < nodes[root].size(); i++){ 
		int next = nodes[root][i];
		if (!visited[next]) { // (2-2단계) 인접한 노드 방문을 위한 재귀함수 호출
			DFS(next);
		} // (3단계) 방문할 노드가 없으면 dfs 종료
	}
}

int main() {
  ...  
  // (4단계) 방문하지 않은 노드에서 DFS 진행
  for (int i = 1; i <= n; i++){
  	if(!visited[i]) {
  		count++;
  		DFS(i);
	  }
  }
 
}

📌Stack을 이용한 DFS 코드

스택으로 구현할 때에는 LIFO(Last-in First-out)의 구조로 인해, 같은 깊이 중에서 탐색하고 싶은 정점을 역순으로 넣어야 원하는 탐색 순서를 얻을 수 있다.

위와 같은 탐색 경로를 스택에 저장하는 경우에
1번을 방문하여 인접한 2, 3, 4를 스택에 넣을 때 순서대로 넣으면
(stack) : 1 - 2 - 3 - 4
순서로 들어있어 top()으로 확인한 값이 2가 아닌 4가 된다. 그래서 i = 0부터 순서대로 그래프를 탐색하고 싶다면 인접한 노드를 역순으로 넣어야 top()으로 2를 확인할 수 있다.
(stack) : 1 - 4 - 3 - 2

for (int i = 1; i <= n; i++){
	if(!visited[i]) {
  		count++;
  		visited[i] = true; // (1단계) 시작 노드 방문 표시
  		vertex.push(i);
  		
  		while(!vertex.empty()){ // (3단계)스택이 빌 때까지 반복
  			int current = vertex.top();
  			vertex.pop();
  			
            // (2단계) current 노드와 연결된 노드를 스택에 역순으로 저장
  			for (int j = nodes[current].size() - 1; j >= 0; j--){
  				int next = nodes[current][j];
  				if(!visited[next]) {
  					visited[next] = true;
  					vertex.push(next);
				  }
			}	
		}
	}
  }

🐣BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 시작 노드에서 인접한 노드를 모두 방문하고 다음 깊이의 노드를 탐색하는 방식이다. (같은 깊이를 먼저 탐색함)

• 큐를 이용하여 구현
• 어떤 노드를 방문했는지 반드시 검사해야 함
• 같은 깊이를 먼저 탐색하기에 최단 거리 탐색에 유리

BFS 구현 방법

1. 시작 노드 방문 (visit 표시)
2. 인접한 노드 탐색
   2-1. 인접한(방문 가능한) 노드가 없으면 큐를 pop() 하여 다음 노드 탐색
   2-2. 인접한(방문 가능한) 노드가 있으면 큐에 넣음 (visit 표시)
3. 큐가 소진될 때까지 2단계 반복

📌Queue를 이용한 BFS 코드

큐는 FIFO(First-in First-out)이기에 같은 깊이의 노드를 넓게 탐색할 수 있다.

for (int i = 1; i <= n; i++){
  	if(!visited[i]) {
  		count++;
  		visited[i] = true; // (1단계) 시작 노드 방문 표시
  		vertex.push(i);
  		
  		while(!vertex.empty()){ // (3단계) 큐가 빌 때까지 반복
  			int current = vertex.front();
  			vertex.pop();
  			
            // (2단계) current 노드와 연결된 노드를 큐에 저장
  			for (int j = 0; j < nodes[current].size(); j++){
  				int next = nodes[current][j];
  				if(!visited[next]) {
  					visited[next] = true;
  					vertex.push(next);
				  }
			}
		}
	}
 }