깊이 우선 탐색(DFS),인접행렬

이번에는 깊이 우선 탐색(DFS, Depth First Search)이라는 알고리즘에 대해 알아보려고 합니다. 일반적으로 이 DFS 알고리즘을 구현할때는 스택을 이용하고, 트리 혹은 그래프 같은 자료구조에서 데이터를 탐색할 때 사용하는 알고리즘 입니다. 너비 우선 탐색이라고 해서 깊이 우선 탐색과 비슷한게 있는데, 너비 우선 탐색은 다음 강좌에서 소개할 예정입니다. 이 DFS 알고리즘은 더이상 나아갈 길이 보이지 않을 만큼 깊이 들어가는 특징을 지니고 있는데, 만약 나아갈 길이 존재하지 않으면 이전의 위치로 돌아와 다른 길을 선택하여 움직입니다. 이해하기 쉽도록 그래프를 보면서 설명을 하도록 하겠습니다

여기서 원으로 둘러싸인 1, 2, 3, 4, 5.. 등을 정점(Vertex)이라 하고, 정점과 정점을 잇는 선을 간선(Edge)라고 하겠습니다. DFS 알고리즘은 인정사정 가릴것 없이, 방문했던 길이 아니라면 아무곳이나 이동합니다. 우선은, 1부터 시작하여 2부터 쭉 방문해 나가도록 하겠습니다.

위의 방문 순서를 보시면 '1 -> 2 -> 4 -> 8 -> 5 -> 6 -> 3 -> 7'과 같은 순서로 방문되고 있음을 보실 수 있는데, 모든 과정을 한번 살펴보도록 하겠습니다.

(1) 현재 위치는 정점 1이고, 정점 2, 3을 방문하지 않았으므로 우선은 정점 2로 이동한다.

(2) 현재 위치는 정점 2이고, 정점 1을 방문했으며, 정점 4, 5를 방문하지 않았으므로 우선은 정점 4로 이동한다.

(3) 현재 위치는 정점 4이고, 정점 2를 방문했으며, 정점 8을 방문하지 않았으므로 정점 8로 이동한다.

(4) 현재 위치는 정점 8이고, 정점 4를 방문했으며, 정점 5, 6, 7을 방문하지 않았으므로 우선은 정점 5로 이동한다.

정점 5로 이동한 후에 정점 2와 정점 8은 이미 방문된 곳이므로 더이상 갈곳이 없으니 전에 방문한 정점으로 돌아간다.

(5) 현재 위치는 정점 8이고, 정점 4, 5를 방문했으며, 정점 6, 7을 방문하지 않았으므로 우선은 정점 6로 이동한다.

(6) 현재 위치는 정점 6이고, 정점 8을 방문했으며, 정점 3을 방문하지 않았으므로 정점 3으로 이동한다.

(7) 현재 위치는 정점 3이고, 정점 1, 6을 방문했으며, 정점 7을 방문하지 않았으므로 정점 7로 이동한다.

(8) 현재 위치는 정점 7이고, 정점 3을 방문했으며, 정점 8번 노드는 이미 방문된 곳이므로 더이상 진행하지 않는다.

 

위 과정을 거친 후에야 이렇게 탐색은 종료되는 것이죠. DFS가 어떻게 움직이는지 감이 잡히시나요? 이번에는 위의 DFS 알고리즘을 코드로 구현하여 보도록 하겠습니다. 코드를 구현하기 전, 정점과 정점 사이의 인접 관계를 나타내기 위해서 인접 행렬(Adjacency Matrix)를 사용하도록 하겠습니다. 우선은 인접 행렬에 대해 간단히 살펴보도록 합시다. 여기서 인접 행렬을 아시고 계시는 분들은 건너뛰셔도 됩니다. 

인접행렬

인접 행렬(Adjacency Matrix)이란 정점의 인접 관계를 행렬을 통해 나타내는 것을 말합니다. 인접 관계를 어떻게 행렬로 표현하는지, 간단한 그래프와 인접 관계를 나타내는 행렬을 아래에다 표시해두도록 했습니다.

만약 정점 i와 정점 j가 서로 연결되어 있는 관계일 경우에는 (i, j)가 1이며, 연결되지 않았을 경우에는 (i, j)에 0이 들어갑니다. 위 그림에서 그래프 옆에 있는 행렬이 인접 행렬이라는 것인데, 대각선을 기준으로 대칭이 됨을 보실 수 있습니다. 만약 정점 1과 정점 3이 연결되어 있는 상태일 경우에는 (1, 3)과 (3, 1)이 1임을 확인할 수 있습니다.

출처: http://blog.eairship.kr/268 [누구나가 다 이해할 수 있는 프로그래밍 첫걸음]