[알고리즘] 5-1. 깊이우선탐색 (DFS)

zzoni·2021년 7월 20일

DFS

Algorithm

목록 보기

5/15

🔵 깊이우선탐색, DFS

▶ Depth-First Search

✔ 그래프 개념

그래프의 가장 기본적인 정의 정점(vertex)과 간선(edge)의 집합
(정점은 노드(node)라고도 흔히들 부름.)

간선은 두 정점을 이어주는 역할을 하며, 자기자신을 이을 수도 있고, 간선에 방향이 있기도 하고 없기도 하며, 가중치가 있기도 하고 없기도 하는 등 아주 다양한 형태의 그래프가 있다.

가장 간단한 형태의 그래프

정점의 집합 V = {1, 2, 3, 4, 5, 6}
간선의 집합 E = {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)}
|V| = 6, |E| = 7

차수(degree)

-> 정점과 이어진 간선의 개수
ex: 1번 정점의 차수는 2, 5번 정점의 차수는 3

✔ 그래프 종류

◾ 무방향 그래프(undirected graph)와 방향 그래프(directed graph)

무방향 그래프는 간선의 방향이 없고, 방향 그래프는 간선의 방향이 있다.
간선의 방향이 없다는 것은 어느 방향으로든 이동할 수 있다는 것이고, 방향이 있다는 것은 화살표 방향으로만 이동할 수 있다는 의미다.

위의 무방향 그래프를 예로 들어, 인접한다(adjacent)는 표현이 있는데 이는 정점 A에서 간선 1개를 거쳐서 정점 B로 이동할 수 있을 때 A와 B가 인접하다고 한다. 두 정점이 간선으로 이어져 있을 때를 얘기하는 것이다. 다만, 무방향 그래프에서는 A, B가 인접하면 B, A도 인접하지만 방향그래프에서는 한쪽만 성립할 수 있다.

방향 그래프에서는 차수를 양분할 수 있다. indegree는 들어오는 간선의 수, outdegree는 나가는 간선의 수다. 또한 방향그래프에서 많이 사용되는 개념 중
cycle이라는 것이 있는데, 간선을 따라가다보니 시작한 정점으로 돌아오는 경로를 말한다. ㄱ->ㄴ->ㄷ->ㄱ 과 같은 식으로 시작점인 ㄱ정점으로 돌아올 수 있는 경로가 싸이클이다.

◾ 가중치 그래프 (weighted graph)

가중치 그래프는 간선들에 가중치가 있다. 이는 비용(weight)일 수도 있고, 두 정점 사이의 거리(distance)를 의미하기도 하며, 때로는 한번에 이동가능한 최대 양인 대역폭(bandweight)를 의미하기도한다. 방향성을 가지면서 가중치 그래프일수도 있다.

◾ 멀티그래프 (multi graph)

똑같은 정점 쌍 (A, B) 사이에 간선이 여러개일 수 있다. 빨간색 간선이 중복되는 간선이다.
정점의 입장에서 반대쪽 정점이 같은 간선이 여러개일 수 있다는 소리이고, 이 때문에 자기 자신으로 돌아오는 (A, A) 같은 간선도 존재하며 이는 파란색으로 표시되어 있다.

✔ 그래프 순회

DFS의 경우는 이름에 걸맞게 한 우물만 깊게 파다가 막히면 그제서야 돌아가서 다른 우물을 파는 성향이 있고, 이는 정반대 성질을 갖는 BFS를 같이 배우시면 더 확연하게 차이점이 드러난다.

DFS가 이루어지는 방식
먼저 정점 하나를 선택한다. 그리고 그 정점의 아직 방문하지 않은 인접한 정점 중 하나를 선택해 방문한다. 여기서 중요한 점은 A가 인접한 B를 방문하면 그 다음번에는 A에 인접한 다른 정점들보다 B에 인접한 정점들에 우선적으로 방문하며 한 우물을 판다!

→ 0번의 인접노드는 1, 2번이다. 더 작은 번호인 1번을 먼저 방문하면, 다음 방문 순서는 2번이 아닌 1번의 인접노드다!

→ 1번의 인접노드인 3, 5 중 방문한다. 더 작은 번호인 3번을 먼저 방문하고,

→ 3번의 인접노드인 4를 방문한다.

→ 5번 노드 하나밖에 선택지가 없다.

이제 5번 노드에서 더 이상 방문할 인접한 노드가 없다. 이 때는 5번에서 추가로 다른 노드를 방문하지 않고, 자기를 불렀던 4번 노드로 돌아가서 4번 노드의 인접 노드들 중 아직 방문하지 않은 정점을 찾아 방문해야한다. 4번에도 없다면 3번으로 거슬러 올라가고... 반복 따라서

→ 0번 노드의 인접한 정점 중 아직 방문하지 않은 나머지 정점 2번 정점을 방문한다. 반복.. 해서 8번 정점을 방문하고 나면, 이제 남은 정점이 없당. 이러면 탐색이 종료된 것이고, 시작점인 0번 노드와 직/간접적으로 연결되어 있는 모든 노드를 탐색한 것이다.

여기서 눈여겨 봐야할 것은 만약 어떤 정점에서 더 방문할 노드가 없다면 자신을 불렀던 정점으로 돌아간다. 이를 스택으로 구현!! 방문하는 순서대로 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 형태로 구현~ (재귀함수를 사용하여도 구현 가능)

👉 dfs 구현 (재귀함수)

위의 내용을 코드로 구현해보면!

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

class Graph {
public:
	int N; //정점의 개수
	vector<vector<int>> adj; //인접 리스트 (간선리스트)
	vector<bool> visited; //방문 여부 저장 배열
	Graph() : N(0){}
	Graph(int n) : N(n) {
		adj.resize(N);
		visited.resize(N);
	}

	//간선 추가함수 (무방향이기 때문에 둘 다 추가)
	void addEdge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	// 모든 리스트의 인접한 정점 번호 정렬
	void sortList() { // 번호가 작은 정점부터 방문하기 위해 만듦
		for (int i = 0; i < N; i++)
			sort(adj[i].begin(), adj[i].end());
	}

	// 깊이 우선 탐색
	void dfs() {
		fill(visited.begin(), visited.end(), false);
		dfs(0); // 0번 노드부터 dfs시작
	}

private:
	void dfs(int cur) {
		visited[cur] = true;
		cout << "node " << cur << " visited\n";
		for (int next : adj[cur])
			if (!visited[next]) dfs(next);
	}
};


int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	Graph G(9);
	G.addEdge(0, 1);
	G.addEdge(0, 2);
	G.addEdge(1, 3);
	G.addEdge(1, 5);
	G.addEdge(3, 4);
	G.addEdge(4, 5);
	G.addEdge(2, 6);
	G.addEdge(2, 8);
	G.addEdge(6, 7);
	G.addEdge(6, 8);
	G.sortList();
	G.dfs();

	return 0;
}

결과

아까 설명과 방문순서가 일치하죠??

✔ 연결그래프

컴포넌트 (component, 연결요소)

그럼 절대 안이어져 있는 정점은 DFS로 방문 불가한가? ㅇㅇ

컴포넌트 하나 안에 속한 정점은 서로 모두 이어져있으며, 다른 컴포넌트끼리는 이어져있지 않다. 또한 컴포넌트는 항상 최대의 크기여야 한다.

이렇게 같은 색의 정점들끼리 하나의 컴포넌트를 이룬다.

연결그래프는 그래프의 컴포넌트가 단 하나인 경우다! 즉, 모든 정점들이 연결되어 있다.

DFS를 한 번 하면 시작점이 속한 컴포넌트의 정점만 다 방문하고 나머지는 절대 방문할 수 없다. 따라서 모든 정점을 방문하려면 각 컴포넌트에 속한 정점들 중 하나씩은 방문시도를 해줘야 하고, 이를 구현하는 가장 쉬운 방법은 반복문을 돌면서 방문하지 않은 정점을 볼 때마다 DFS를 시작해 주는 것이다.
또한, 이때 방문을 시도하는 횟수가 컴포넌트의 개수가 된다.

◼ 연결그래프 dfs

예를 들어, 위 그래프에서 dfs를 해보자~
위 코드에서 void dfs() 코드를 int dfsAll()로 바꿔주었다.

int dfsAll () {
		int components = 0;
		fill(visited.begin(), visited.end(), false);
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				cout << "-- new DFS begins --\n";
				dfs(i);
				components++;
			}
		}
		return components;
	}

그리고, main의 코드도 아래코드로 바꿔주었다.

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	Graph G(10);
	G.addEdge(0, 1);
	G.addEdge(1, 3);
	G.addEdge(2, 3);
	G.addEdge(4, 6);
	G.addEdge(5, 7);
	G.addEdge(5, 8);
	G.addEdge(7, 8);
	G.sortList();

	int components = G.dfsAll();
	cout << "The number of component is " << components << endl;

	return 0;
}

결과

◾ 각 컴포넌트의 크기

위 코드에서 각 컴포넌트의 크기까지 구해버려보자.

	int dfsAll () {
		int components = 0;
		fill(visited.begin(), visited.end(), false);
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				cout << "-- new DFS begins --\n";
				int nodes = dfs(i);
				components++;
				cout << "size: " << nodes << "\n\n";
			}
		}
		return components;
	}

	int dfs(int cur) {
		int nodes = 1;
		visited[cur] = true;
		cout << "node " << cur << " visited\n";
		for (int next : adj[cur])
			if (!visited[next]) nodes += dfs(next);
		return nodes;
	}