DFS

그동안 3개의 포스팅을 통해 그래프를 다뤘습니다. 

이제 그래프를 탐색하는 알고리즘 중 가장 유명한 DFS, BFS 중 DFS 먼저 다뤄봅시다.

DFS (Depth First Search)

깊이우선탐색, 특정 노드부터 시작해 인접한 노드들을 재귀적으로 방문합니다.

이때, 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색합니다.

(분기란? : 2개 이상으로 정점이 쪼개지는 지점)

 

 

pseudocode (수도코드 - 의사코드)

DFS(u, adj)
    u.visited = true
    for each v ∈ adj[u]
        if v.visited == false
            DFS(v, adj)

 

시작 정점 u부터 방문하여, u와 인접한 모든 노드들에 대해 방문하지 않았으면 해당 노드를 방문한다.

예시를 하나 들어봅시다. 아래의 그림과 같은 트리가 존재한다고 가정합시다. 

 

그럼 DFS는 다음과 같은 순서로 실행됩니다(들립니다)

u → a → c → e → d → b

 

재귀적으로 점점 깊은 노드로 내려가다가, 더 이상 내려갈 곳이 없으면 리턴하며 돌아옵니다.

그리고 다시 분기점에서, 다른 노드를 살펴보고 방문하지 않았으면 해당 노드(d)를 방문합니다.

이후 다시 리턴하며 돌아오다가, 시작점(일종의 분기점)에서 방문하지 않은 b를 방문하게 됩니다.

 

이제 dfs를 코드로 구현하면 다음과 같습니다. 

(아래의 예시는, 위의 그림과는 다른 예시입니다. 1, 2, 3, 4, 5 라는 이름의 노드가 존재합니다)

#include<iostream>
#include <vector>

//인접 리스트로 표현된 그래프
using namespace std;
const int n = 6;
vector<int> adj[n];
int visited[n];

void DFS(int u) {
	//시작점도 반드시 방문처리
	visited[u] = 1;
	cout << u << "\n";
	for (int v : adj[u]) {
		if (visited[v] == 0) {
			DFS(v);
		}
	}
	cout << u << "로부터 시작된 함수가 종료되었습니다.\n";
	return;
}
int main() {
	//인접리스트 구성
	adj[1].push_back(2);
	adj[1].push_back(3);
	adj[2].push_back(4);
	adj[4].push_back(2);
	adj[2].push_back(5);

	//dfs 실행
	DFS(1);
}

 

아, 참고로 방문하는 시점과 함수가 종료되는 시점은 다르다는 건 알고 계시죠?

가장 먼저 실행된 함수는 가장 늦게 반환이 됩니다. (call stack 이기 때문)

따라서 저 cout 의 위치가 어디냐에 따라 print 되는 시점도 달라지니, 무언가 dfs로 작업할 때 유의하세요!

 

또한, 시작점 방문 처리도 필수!! 입니다. 물론 시작점 방문 처리는 DFS를 호출 전에 해줄 수도 있긴 한데, 그럼 코드가 좀 더 길어지고 통일성이 떨어진다는 아쉬움이 있어요. 그래서 DFS 함수 안에서 방문처리하는 것을 추천합니다.

 

 

DFS 구현 방법 2가지 - 신중하게 혹은 거칠게

2가지 방법은 (1)신중하게 방문하는 방법, (2) 거칠게 방문하는 방법 으로 나눌 수 있습니다.

 

(1) 신중하게 방문하는 방법

신중하게 방문하는 방법은 방문 여부를 확인한 뒤 방문하는 방법입니다.

void DFS(int here) {
	visited[here] = 1;
	for (int there : adj[here]) {
		if (visited[there]) continue;
		DFS(there);
	}
}

---------------------------------------------------혹은--------------------------------------

//다만 이 경우에는, 방문하기 전에 visited 처리를 해주어야만 한다 -> 실수 가능성 존재
void DFS(int here){
    for(int there : adj[here]){
        if(visited[there]) continue;
        visited[there] = 1;
        DFS(there);
    }
}
//반드시 시작점을 방문 처리 해준다음에 DFS를 호출해야한다
visited[1] = 1;
DFS(1);

 

(2) 거칠게 방문하는 방법

거칠게 방문하는 방법은, 방문 여부를 확인하지 않고 일단 방문해본 뒤에, 방문 되어 있으면 나가는 방법입니다.

void DFS(int here) {
	if (visited[here]) return;
	visited[here] = 1;
	for (int there : adj[here]) {
		DFS(there);
	}
}

 

 

문제에 따라 (1) 혹은 (2) 중 편한 방식이 다를 수 있으니, 2개의 방식 전부 알아둬야 합니다.

 

 

DFS 문제 예시 

이제 간단한 문제를 풀어보며 DFS에 익숙해져 봅시다. 이 문제에는 맵, 방향 벡터, DFS를 결합했습니다.

힌트를 드리자면, 연결된 컴포넌트를 찾아야하는 문제입니다.

 

문제 설명

준혁은 독 안개를 퍼뜨리는 마법의 지팡이를 지니고 있습니다. 그가 지팡이를 한 번 휘두르면, 독 안개가 상하좌우 네 방향으로 퍼져나가며 준혁이 지팡이를 휘두른 지점과 연결된 "육지"는 모두 독 안개로 뒤덮입니다. 그러나 독 안개는 "바다"로는 퍼질 수 없습니다. 맵이 주어졌을 때, 준혁이 지팡이를 최소한 몇 번 휘둘러야 모든 육지를 뒤덮을 수 있는지 구하세요.

 

입력

맵의 세로 길이 N과 가로 길이 M이 주어지고, 이어서 N×M 크기의 맵이 주어집니다.

• 1은 육지를, 0은 바다를 나타냅니다.

출력

모든 육지를 뒤덮기 위해 준혁이 지팡이를 휘둘러야 하는 최소 횟수를 출력하세요.

 

범위

1 <= N <= 100

1 <= M <= 100

 

예제 입력

5 5 1 0 1 0 1 1 1 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0

 

예제 출력

4

 

 

정답 코드

#include <iostream>
#include <vector>
using namespace std;

//N * M 크기의 맵
int N, M;

//상,하, 좌, 우로 구성
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

//map과 visited 배열 구성
int map[100][100];
bool visited[100][100];

//2차원이니까 2개의 인자 필요
void DFS(int y, int x) {
	//dfs 퍼져나가는게 잘 상상이 안가면, 이 위치에 print문 적어서 디버깅해보기!
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
		if (map[ny][nx] == 1 && !visited[ny][nx]) {
			DFS(ny, nx);
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int ans = 0;

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	//모든 노드에 대해 실행해봄 
	// (한 노드에 방문하면 connected component에 속한 노드들이 전부 방문 처리됨)
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				ans++;
				DFS(i, j);
			}
		}
	}
	cout << ans << "\n";

	return 0;
}

 

2가지 포인트에 집중해야합니다. connected component의 수를 파악하기 위해 모든 노드에서 DFS를 시도해보려고 하는 for문을 main에 작성했다는 점, 그리고 map이나 visited를 사용할 때 y와 x의 순서를 절대 헷갈리지 말 것! (사실 저도 풀다가 순간 visited[nx][ny] 로 접근해서 비정상 종료가 되었었습니다.)