Chapter 4-3. 그래프 순회 방법 1️⃣ - DFS(깊이 우선 탐색)
카테고리: Algorithm Lesson 2
인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click
Chapter 4. 그래프
🚖 그래프 순회 방법
배열이나 리스트는 선형 자료 구조이므로 원소들을 차례대로 순회하면 되지만 그래프는 선형 자료 구조가 아닌, 한 정점에 연결된 정점들이 여러개일 수 있으므로 연결된 정점들 중 다음엔 어떤 정점을 탐색할지 다르므로 순회 방법이 다양하다. 대표적으로 두 가지가 있다.
- 그래프 순회 방법
- DFS (Depth First Search 깊이 우선 탐색)
- 들어갈 수 있다면 무조건 들어가며 깊이 들어감
- 끝까지 들어가야 다시 돌아 옴
- BFS (Breadth First Search 너비 우선 탐색)
- DFS (Depth First Search 깊이 우선 탐색)
🚖 DFS
1️⃣ 배열로 구현된 그래프 DFS 순회
class Graph
{
int[,] adj = new int[6, 6]
{
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0 },
{ 1, 1, 0, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0 },
};
bool[] visited = new bool[6]; // 방문 체크를 위해
public void DFS(int now) // 순회 시작 위치가 인수로 들어 옴
{
// 1) now 부터 방문 하고
Console.WriteLine(now);
visited[now] = true;
// 2) now 와 연결된 정점들을 하나씩 확인해서, [ 아직 미 방문 상태라면 ] 방문한다.
for (int next = 0; next < 6; next++)
{
if (adj[now, next] == 0) // 연결 되어 있지 않으면 스킵
continue;
if (visited[next]) // 이미 방문 했으면 스킵
continue;
DFS(next); // 재귀 (깊이 들어 감)
}
}
}
class Program
{
static void Main(string[] args)
{
Graph graph = new Graph();
graph.DFS(3); // 3 0 1 2 4 5
}
}
- 일단 방문 체크를 한다.
- 연결이 되어 있으며, 아직 방문하지 않은 곳이라면 깊이 들어가 방문한다.
- 배열은 연결 되어 있지 않은 정보도 포함되어 있기 때문에 (
0) 연결 되어 있는지 즉 갈 수 있는지를 체크해주어야 한다. - 갈 수 있는 곳이라면 깊이 들어간다. 👉 재귀 함수 호출
- 배열은 연결 되어 있지 않은 정보도 포함되어 있기 때문에 (
DFS(3) 3 에서 DFS 순회를 시작했다면 3 0 1 2 4 5 순으로 방문하게 될 것이다.
2️⃣ 리스트로 구현된 그래프 DFS 순회
class Graph
{
List<int>[] adj2 = new List<int>[]
{
new List<int>() { 1, 3 },
new List<int>() { 0, 2, 3 },
new List<int>() { 1 },
new List<int>() { 0, 1, 4 },
new List<int>() { 3, 5 },
new List<int>() { 4 },
};
bool[] visited = new bool[6];
public void DFS2(int now)
{
// 1) now 부터 방문 하고
Console.WriteLine(now);
visited[now] = true;
// 2) now 와 연결된 정점들을 하나씩 확인해서, [ 아직 미 방문 상태라면 ] 방문한다.
foreach (int next in adj2[now])
{
if (visited[next]) // 이미 방문 했으면 스킵
continue;
DFS2(next);
}
}
}
class Program
{
static void Main(string[] args)
{
Graph graph = new Graph();
graph.DFS2(0); // 0 1 2 3 4 5
}
}
- 일단 방문 체크를 한다.
- 아직 방문하지 않은 곳이라면 깊이 들어가 방문한다.
- 리스트는 나와 연결 되어 있는 정보만 갖고 있기 때문에 연결 되어 있는지를 체크할 필요는 없다.
- 갈 수 있는 곳이라면 깊이 들어간다. 👉 재귀 함수 호출
DFS2(0) 3 에서 DFS 순회를 시작했다면 0 1 2 3 4 5 순으로 방문하게 될 것이다.
3️⃣ 연결이 끊겨 있는 부분이 있는 그래프 DFS 순회
int[,] adj = new int[6, 6]
{
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0 },
{ 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0 },
};
adj[3][4], adj[4][3] 값을 0 으로 바꾸어 3, 4 정점간의 연결을 끊어 준다.
class Graph
{
int[,] adj = new int[6, 6]
{
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0 },
{ 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0 },
};
bool[] visited = new bool[6];
public void DFS(int now)
{
// ...
}
public void SearchAll()
{
visited = new bool[6]; // 전부 false로 초기화
for (int now = 0; now < 6; now++)
{
if (visited[now] == false)
DFS(now);
}
}
}
class Program
{
static void Main(string[] args)
{
Graph graph = new Graph();
graph.SearchAll(); // 0 1 2 3 4 5
}
}
now = 0👉 DFS(0)- 이 호출 하나가 끝났을 땐, visited[0], visited[1], visited[2], visited[3] 의 값은
true로 바뀌어 있다.- 0 을 시작으로 깊이 들어가 0, 1, 2, 3 정점을 모두 방문했기 때문.
now값이 1, 2, 3 일땐 if (visited[now] == false) 걸리지 않는다. (생각보다 if문이 자주 호출되진 않음. DFS(0) 호출 한번으로 0, 1, 2, 3 을 모두 방문하게 되기 때문)
- 이처럼 연결만 되어 있다면 정점 하나로 연결된 모든 정점들을 DFS 순회법으로 전부 방문할 수 있다.
- 0 을 시작으로 깊이 들어가 0, 1, 2, 3 정점을 모두 방문했기 때문.
- 이 호출 하나가 끝났을 땐, visited[0], visited[1], visited[2], visited[3] 의 값은
now = 4👉 DFS(4)- 이 호출 하나로 visited[4], visited[5] 방문
- 이처럼 연결이 끊겨 있는 그래프를 전부 방문하기 위해 이와 같은 방법을 사용할 수 있다.
- 한번의 DFS 순회로 연결 되어 있는 노드는 다 방문할 수 있기 때문에 if (visited[now] == false) 방문 되지 않은 정점을 검사한다는 의미는, 연결이 끊겨 있는 곳이 있을 것을 대비해서다.
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기