그래프 탐색방법 - DFS

알고리즘을 풀때 그래프를 탐색하는 목적은  모든 정점을 한번씩 탐색한다는 것이다. 

그래서 두가지 그래프 탐색방법이 존재하는데 하나는 DFS (깊이 우선 탐색) 이고 나머지는 BFS(너비 우선 탐색)이다. 

이번포스트는 두가지에 대해 하나씩 설명하고 백준에 있는 간단한 문제를 한번 풀어보려 한다.

○ DFS(깊이 우선 탐색)

깊이 우선 탐색이란 최대한 깊게 나가 그래프를 탐색하는 방법을 말한다.

 다시말해 스택을 이용해 최대한 많이 가고, 더이상 갈 수 없으면 이전 정점으로 돌아가는 방법이다.

이해가 쉽도록 그림을 이용해 설명하겠다.

다음과 같은 그래프가 존재한다고 가정하자  만약 다음 스택에 갈 수 있는 방향이 여러가지라면 가장 작은 값부터 가는것을 원칙으로 하고 설명을 하겠다.

i	1	2	3	4	5	6
Check[i]	1	0	0	0	0	0

다음과 같이 방문을 하면 check의 값에 1을 넣어 중복해서 방문하지 않게 하기위한 조치를 취해둔다.

현재 정점	1
순서	1
스택	1

이렇게 보기 좋게 정리를 하고 순서대로 정점과 체크 값의 변화를 정리해 보겠다. 

i

1

2

3

4

5

6

Chec

1

1

1

0

0

0

현재 정점	2
순서	1 2
스택	1 2

i	1	2	3	4	5	6
Check[i]	1	1	1	0	0	0

현재 정점	3
순서	1 2 3
스택	1 2 3

i	1	2	3	4	5	6
Check[i]	1	1	1	1	0	0

현재 정점	4
순서	1 2 3 4
스택	1 2 3 4

i	1	2	3	4	5	6
Check[i]	1	1	1	1	1	0

현재 정점	5
순서	1 2 3 4 5
스택	1 2 3 4 5

여기까진 순서대로 진행하는데  5 다음에 지나갈 모든 정점이 다 이미 지났던 곳이다. 이럴땐 스택을 pop 해 한칸 뒤로 가고 다른 정점으로 이동한다.

또한 그냥 뒤로 가는 것이기 때문에 check의 값의 변화는 없다. 

현재 정점	4
순서	1 2 3 4 5
스택	1 2 3 4

새로 갈수 있는 정점이 나왔기에 다시 6번으로 가면된다.

i	1	2	3	4	5	6
Check[i]	1	1	1	1	1	1

현재 정점	6
순서	1 2 3 4 5 6
스택	1 2 3 4 6

더이상 갈 곳이 없기 때문에 pop을 하면서 새로 갈 수 있는 곳을 찾는다.

현재 정점	4
순서	1 2 3 4 5 6
스택	1 2 3 4

   

현재 정점	3
순서	1 2 3 4 5 6
스택	1 2 3

현재 정점	2
순서	1 2 3 4 5 6
스택	1 2

현재 정점	1
순서	1 2 3 4 5 6
스택	1

현재 정점
순서	1 2 3 4 5 6
스택

스택이 비게 되면 DFS의 탐색은 종료가 된다.

위에 대해 코드를 통해 나타내면 다음과 같다.

void dfs(int x){

    check[x] = true;

//// 인접행렬로 구현

    for(int i=0; i<=n; i++){ // 다음 정점을 찾는 과정

        if a[x][i] == 1 & check[i] == false; // x->i로 가는 간선이 있고 체크 값이 0일때 간선으로 간다는 것이다.

        dfs(i);

    }

    

// 인접 리스트로 구현

    

//    a[x] 에는 x 와 연결된 정점의 개수

//    그래서 size를 통해 정점이 있는것만 파악이 가능하다.

    for(int i=0; i<a[x].size(); i++){

        int y = a[x][i];

        if (check[y] == false){

            dfs(y);

        }

    }

}