[알고리즘] 깊이우선 탐색, 너비우선 탐색

깊이우선 탐색

---

트리나 그래프와 같은 비선형구조는 어떤 문제 상황이나 가능한 답들과 그 관계들로 생각할 수 있습니다. 깊이우선 탐색(Depth First Search)은 어떤 정점을 방문한 후, 그 정점에 연결된 다른 정범으로 파고 들어가는 형태의 탐색 방법입니다.

깊이 우선 탐색은 가능한 가장 깊이 들어갔다가 더이상 파고들어갈 수 없을때 이전상태로 복귀하고 파고들어가고 나오고를 반복하는 형태입니다. 반면, 너비우선 탐색방법은 어떤 방점에서 연결된 가장 빠른 정점들을 방문한 후에 다시 같은 방법들을 연결된 순서들을 다시 방문해 나가는 방법입니다.

깊이우선 탐색 (Depth First Search) : 어떤 정점을 방문하여 확인한 후 그 정점과 연결된 정점들 중에서 우선 순위가 가장 빠른 하나를 선택해 방문해 나가는데, 더 이상 방문할 곳이 없으면 이전 상태로 되돌아가는 탐색 방법

깊이우선 탐색은 재귀함수의 호출/실행 과정과 완전히 똑같다.

백트랙(backtrack) : 스택(stack) 구조나, 재귀(recursion) 함수를 이용

깊이우선 탐색 순회 방법: 루트에서 우선순위가 가장 높은 자식노드를 방문합니다. 추가 자식노드가 있다면 더 내려가다 더이상 방문할 노드가 없다면 이전상태로 복귀하고, 그곳에서 가능한 방문하지 않은 다른 곳을 방문하는 방식입니다.

이러한 방법으로 비선형구조의 모든 정점들을 체계적으로 방문하게 됩니다.

정리하자면, 깊이우선 탐색은 시장 정점에서 어떤 우선순위에 따라 연결된 다른 정점으로 이동할 수 있을 때까지 계속해서 이동하면서 진행합니다. 더이상 진행할 수 없다면 이전 정점으로 백트랙하여 다시 다른 정점으로 진행하고, 모든 정점을 탐색할 때까지 반복적으로 검사하는 전체 탐색 방법입니다.

여기서 백트래킹은 모든 비선형구조 문제에 대해 적용할 수 있는 가장 기본적인 방법입니다.

핵심코드(인접행렬 구조의 깊이 우선탐색, 2차원배열 사용, 구현 간단)

bool visited[101];
void dfs(int k)
{
    for(int i=1; i<=n; i++) {
        if( G[k][i] && !visited[G[k][i]] )
        {
            visited[G[k][i]] = true;
            dfs(G[k][i]);
        }
    }
    return;
}

핵심코드(인접리스트 구조의 깊이우선 탐색, 벡터 리스트사용, 속도 빠름)

bool visited[101];  //방문했던 위치 저장
void dfs(int k)
{
    for(int i=0; i<=G[i].size(); i++) {
        if( !visited[G[k][i].to] )
        {
            visited[G[k][i].to] = true;
            dfs(G[k][i]);
        }
    }
    return;
}

4: k번 정점에 연결될 수 있는 모든 n가지 연결의 경우에 대해서

5: 정점에 값이 있는데 방문하지 않았다면

7: 방문했다고 기록하고

8: 다시 그 점으로 이동해서 깊이우선 탐색 시작

11: k번 정점에서 연결된 모든 정점을 방문했다면, 이전 상태로 돌아감

[문제] 정올이는 땅속의 굴이 모두 연결되어 있으면 이 굴은 한마리의 두더지가 사는 집이라는 사실을 발견하였다. 정올이는 뒷산에 사는 두더지가 모두 몇 마리인지 궁금해졌다. 정올이는 특수 장비를 이용하여 뒷산의 두더지 굴을 모두 나타낸 지도를 만들 수 있었다. 이 지도는 직사각형이고 가로 세로 영역을 0 또는 1로 표현한다. 0은 땅이고 1은 두더지 굴을 나타낸다. 1이 상하좌우로 연결되어 있으면 한마리의 두더지가 사는 집으로 정의할 수 있다.

[그림2]는 [그림1]을 두더지 굴로 번호를 붙인 것이다. 특수촬영 사진 데이터를 입력받아 두더지 굴의 수를 출력하고, 각 두더지 굴의 크기를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력) 첫번째 줄에 가로, 세로의 크기를 나타내는 n이 입력된다. n은 30이하의 자연수 두 번째 줄부터 n줄에 걸쳐서 n개의 0과 1이 공백으로 구분되어 입력된다.

출력) 첫째 줄에 두더지 굴의 수를 출력한다. 둘째 줄부터 각 두더지 굴의 크기를 내림차순으로 한 줄에 하나씩 출력한다.

입력 예	출력 예
7  0 1 1 0 1 0 0  0 1 1 0 1 0 1  1 1 1 0 1 0 1  0 0 0 0 1 1 1  0 1 0 0 0 0 0  0 1 1 1 1 1 0  0 1 1 1 0 0 0	3  9  8  7

문제 해결) 지도의 각 칸을 정점으로 생각한다. 위, 아래, 왼쪽, 오른쪽에 1로 연결되어 있다면, 그 사이에 간선이 있는 것이라고 생각

입력 예	대응되는 그래프
7  0 1 1 0 1 0 0  0 1 1 0 1 0 1  1 1 1 0 1 0 1  0 0 0 0 1 1 1  0 1 0 0 0 0 0  0 1 1 1 1 1 0  0 1 1 1 0 0 0

배열의 (0,0)부터 하나씩 순차탐색을 진행, 어떤 위치의 값이 1인 곳이 나타나면 그 위치를 시작으로 깊이우선 탐색을 진행한다. 그렇게 얻어진 두더지 굴의 크기를 적당히 저장해 둔 후, 마지막에 STL 라이브러리의 정렬인 std::sort()를 이용해 내림차순으로 출력한다.

[두더지 = 2]

두저지의 값은 2부터 시작 1은 주인없는 굴이므로 2부터 증가한다. (0,0)에서 탐색을 시작하고, (0,0)의 원소가 0이므로 통과한다. Size 배열은 각 두더지 집의 크기를 저장할 배열이다.

(0,1)을 탐색, 원소의 값이 1이므로 dfs를 이용하여 상, 하, 좌, 우로 연결된 그래프를 모두 탐색하여 2로 수정한다. 방문한 정점의 수인 7을 Size[2]에 기록하여 크기를 저장하고, 두더지 값 1 증가

[두더지 = 3]

(0,2)를 탐색, 원소의 값이 원래 1이었으나 (0,1)에 의해 2로 바뀌었으므로, 이미 다른 두더지의 굴에 포함되었음. 따라서 그냥 통과!

(0,3), (0,4)는 모두 패스, (0,5)에서 다시 1이 등장하므로 이점을 기준으로 dfs로 flood fill을 수행하면 상, 하, 좌, 우의 모든 칸 들이 3으로 바뀜. Size[3]을 방문한 정점의 수인 8로 채우고, 두더지의 값 1 증가

[두더지 = 4]

(0, 6)부터 (4,0)까지는 1이 하나도 없으므로 모두 패스. (4,1)에서 1이 등장하므로 이 칸으로부터 dfs를 모든 영역을 4로 채움. 그리고 방문한 정점의 수를 Size[4]에 기록함, 두더지 값은 5가 됨.

[두더지 = 5]

마지막 칸까지 1의 값이 없으므로 모든 작업 종료. 세 마리 두더지가 있었고, 각 굴의 크기는 7, 8, 9임을 알 수 있음.

핵심코드 설명

void dfs(int a, int b, int c)
{
    A[a][b] = c;
    if( safe(a+1, b) && A[a+1][b] == 1 )
        dfs(a+1, b, c);
    if( safe(a-1, b) && A[a-1][b] == 1 )
        dfs(a-1, b, c);
    if( safe(a, b+1) && A[a][b+1] == 1 )
        dfs(a, b+1, c);
    if( safe(a, b-1) && A[a][b-1] == 1 )
        dfs(a, b-1, c);
}

1: (a,b)에서 시작해서 연결된 모든 정점들의 값을 c로 바꾼다.

3: c로 값 기록하기

4,6,8,10: 지도 안쪽이면서 아래, 위, 오른쪽, 왼쪽이 1인 경우

5,7,9,11: 그 위치로 이동해서 다시 기ㅏㅍ이우선 탐색 진행

너비우선 탐색

---

너비우선 탐색은 어떤 정점을 방문한 후, 그 정점에 연결된 다른 정점들을, 방문 대기 줄에 순서대로 줄을 세워 두는 방법으로 가장 가까운 정점들부터 순서대로 방문하기 위해 특별한 구조를 사용해야 함.

깊이우선 탐색의 경우 어떤 것들이 연결되어있을때 우선순위에 따라서 연결될 수 있는 마지막까지 이동하다가 더이상 진행할 수없다면 이전상태로 이동해서 다시 진행하는 방식입니다. 반면 너비우선 탐색은 일단 어떤 정점에서 갈수있는 노드를 순서대로 저장시켜 둡니다. 마치, 은행에서 줄을 서는 것과 같은 효과를 나타냅니다(Queue 구조)

a

b

c

d

e

f

g

h

i

j

k

너비우선 탐색: 어떤 정점을 방문하여 확인한 후, 그 정점과 연결된 정점들 중에서 우선 순위에 따라 줄을 세워 방문해 나가는데, 한 정점을 방문하고 나면 세워진 줄의 맨 앞 정점을 골라 같은 방법으로 계속 줄을 세워 모두 탐색하는 방법입니다.

너비우선 탐색은 큐(queue)라는 자료구조를 사용해 같은 깊이/레벨에 있는 모든 정점들을 방문하고 난 후, 다음 깊이/레벨의 정점들을 순서대로 방문해 나가는 형태를 띄게 됩니다. 큐(queue) 자료 구조를 사용하기 위해서는 STL 라이브러리의 std::queue를 사용하면 됩니다.

핵심코드(인접행렬 사용 그래프 저장, 큐를 사용하는 너비우선 탐색)

#include <queue>
bool visited[101];
void bfs(int k)
{
    std::queue<int> Q;
    Q.push(k), visited[k] = 1;
    while(!Q.empty())
    {
        int current=Q.front(); Q.pop();
        for(int i=1; i<=n; i++) {
            if(G[current][i] && !visited[G[current][i]])
            {
                visited[G[current][i]]=1;
                Q.push(G[current][i]);
            }
        }
    }
}

1: std::queue를 이용하기 위함

2: 방문했는지 체크해 두는 배열

5: Queue를 선언

6: 출발 정점을 Queue에 삽입

7: Queue가 빌때까지 반복

9: Queue에서 하나 삭제

10: 모든 정점에 대해 검사

11: 검사하는 정점이 현재 정점과 연결되어 있고, 아직 방문하지 않았으면

13: 체크후 Queue에 추가

위 두더지 문제를 너비우선 탐색에서도 적용할 수 있음.

문제 해결) 배열의 (0,0)부터 하나씩 순차탐색을 진행, 어떤 위치의 값이 1인 곳이 나타나면 그 위치를 시작으로 너비우선 탐색을 진행

그렇게 얻어진 두더지 굴의 크기를 적당히 저장해 둔 후,

마지막에 STL 라이브러리의 정렬인 std::sort()를 이용해 내림차순으로 출력

이렇게 연결된 부분을 너비우선 탐색방법으로 플러드 필(flood fill) 할 수도 있다.

void bfs(int a, int b, int c)
{
    std:queue<VERTEX> Q;
    Q.push((VERTEX){a, b}), A[a][b]=c;
    while(!Q.empty())
    {
        VERTEXT curr = Q.front(); Q.pop();
        for(int i=0; i<4; i++) {
            if(safe(curr.a+dx[i], curr.b+dy[i]) &&
                A[curr.a+dx[i]][curr.b+dy[i]]==1)
            {
                A[curr.a+dx[i]][curr.b+dy[i]] = c;
                Q.push((VERTEX){curr.a+dx[i], curr.b+dy[i]});
            }
        }
    }
}

1: (a,b)에서 시작해서 연결되 모든 정점들의 값을 c로 바꾼다.

3: 탐색 순서를 줄 세워, 좌표값으로 저장할 큐 만들기

4: (a,b)를 큐에 집어넣고 좌표 값을 c로 기록

5: 줄을 서있는 좌표가 더 이상 없을 때까지

7: 대기 줄(큐)의 가장 앞쪽 좌표를 끄집어 내서

8: 그 좌표의 4방향에 대해서

9~10: 맵 안쪽이면서 1이면

12: 그 배열의 값을 c로 바꾸고

13: 그 좌표에 연결된 4개의 방향을 큐(대기 줄)의 맨 끝에 줄을 세움

코드가 어려워보워도 실제 그림을 그리면서 해야 이해가 갈 수 있다.

깊이/너비우선 탐색 방법은 트리/그래프와 같은 비선형 구조의 자료 탐색에서 어떤 데이터나 상황에 연결된 여러 가지 경우를 모두 탐색하기 위해 효과적으로 사용될 수 있습니다. 재귀함수 형태로 설계된 함수는 실행 과정에서 함수의 호출이 스택에 저장되며, 깊이우선 탐색 형태로 실행됩니다. 너비우선 탐색 방법을 구현하기 위해서는 탐색할 순서를 저장해 두기 위해 큐(queue)라는 자료구조를 사용할 수 있습니다.