[C++#4-1] DFS

DFS에 대해 작성한 이 글에서는 글을 읽는 사람들이 그래프, 스택에 대한 기본적인 지식이 있다고 생각하고 작성했다.

1. DFS(Depth-First Search)

사전에서 정의하는 DFS의 정의는 아래와 같다.

깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

다음과 같은 그래프가 있다고 생각해보자.

그래프의 모든 정점을 순회하고자 할 때, 정점을 순회하는 방법은 여러가지가 있을 것이다.

DFS는 여러갈래의 길이 있을 때, 하나의 길 씩 탐색하는 방법이다.

DFS는 위의 그림처럼 여러 갈래길이 있을 때, 하나의 길부터 갈수 있는 최대한 깊이 탐색한 후에, 다른 길을 탐색한다.

아래 영상을 보면 좀더 이해가 쉬울 것이다.

1-1. 그래프

글의 시작에서도 스택에 대해서 언급했다싶이 DFS는 스택을 사용한다.

스택에는 다음에 탐색할 정점 or 위치를 저장(push)하고, 다음에 탐색할 정점이 없다면 스택에서 해당 정점을 삭제(pop)한다.

위의 그래프를 DFS로 탐색하는 과정은 아래와 같다.

먼저 시작점인 정점 1을 스택에 push 해준다.

정점 1에서 갈수 있는 가장 낮은 정점 2를 push해주고, 

정점 2에서 갈 수 있는 가장 낮은 정점 3을 push해준다.

정점 3에서 다시 정점 7을 push 해주고,

정점 7에서 가장 낮은 정점 4를 push해준다.

정점 4에서 가장 낮은 정점 5를 push해주고,

정점 5에서 갈 수 있는 유일한 정점 6을 push해준다.

정점 6에선 더이상 탐색할 수 있는 정점이 없다.

여기까지가 처음 글에서 말했던 여러 갈래길에서 하나의 갈래길이다.

정점 6에서 더이상 탐색이 불가능하므로, 6을 pop한다.

정점 5에서 또한 탐색이 불가능 하므로 pop을 해준다.

정점 4에서 탐색할 수 있는 정점인 정점 8을 push해준다.

정점 8에서 탐색할 수 있는 정점인 정점 9를 push 해준다.

탐색이 불가능하므로 정점 9를 pop한다.

마찬가지로 정점8, 

정점 4,

정점 7,

정점 3,

정점 2,

정점 1을 pop해주고, 스택이 비어있으므로 탐색을 종료한다.

1-2. 코드

DFS를 코드로 구현하기 전에 우리는 2차원 배열에서의 DFS에 대해서 먼저 생각해볼 것이다.

그래프를 이용해서도 여러가지 맵을 구현할 수는 있긴 하지만, 코딩테스트 문제에선 주로 2차원배열을 이용한 맵이 주어진다.

그래서 우리는 아래와 같은 맵에서 목적지까지 도달하는 최단 경로를 DFS로 구현할 것이다.

여기서 S는 출발점, F는 도착점을 나타낸다.

일단 전체적인 코드는 아래와 같다.

#include <iostream>
 
using namespace std;
 
int map[5][5] = { { 0, 0, 0, 0, 0 },
                    { 1, 1, 0, 1, 0 },
                    { 0, 0, 0, 0, 0 },
                    { 0, 1, 0, 1, 1 },
                    { 0, 0, 0, 0, 0 } };
 
int checkmap[5][5]{ { 0, 0, 0, 0, 0 },
                    { 0, 0, 0, 0, 0 },
                    { 0, 0, 0, 0, 0 },
                    { 0, 0, 0, 0, 0 },
                    { 0, 0, 0, 0, 0 } };
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0,-1 };
 
int min_n = 25;
void dfs(int y, int x, int cnt);
 
 
int main() {
    dfs(0, 0, 0);
 
    cout << min_n << endl;
}
 
void dfs(int y, int x, int cnt) {
    if (y == 4 && x == 4) {
        if (min_n > cnt)min_n = cnt;
    }
 
    checkmap[y][x] = 1;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if (ny < 0 || ny > 4 || nx < 0 || nx > 4 || map[ny][nx] == 1) continue;
        if (checkmap[ny][nx] == 1) continue;
        dfs(ny, nx, cnt + 1);
        
        checkmap[ny][nx] = 0;
    }
}
 

1-2-1. Stack?

코드를 보면 당황스러울 수도 있을 것이다.

우리는 좀전의 그래프에서 스택에서 정점을 하나씩 push, pop을 통해 탐색을 했는데, 스택에 대한 내용이 하나도 없기 때문이다.

스택의 특징은 LIFO(Last-In-First-Out)특징을 갖는다.

DFS를 스택으로도 구현할 수도 있지만, 이 코드에선 재귀를 통해서 DFS를 구현했다.

재귀함수에서 새로운 재귀함수를 호출하면 새롭게 호출된 재귀함수가 먼저 종료되고,

그 후에 이전의 재귀함수가 종료되며, 최종적으로 처음에 호출했던 재귀함수가 종료되고 재귀가 종료된다.

마지막(Last)에 실행(In)된 것이 가장 먼저(First) 종료(Out)되고, 처음에 실행된 것이 마지막에 종료되는 구조인 것이다.

이 DFS코드에서 재귀함수는 스택의 기능으로 사용된다는 점을 알면, 어렵지 않게 DFS를 구현할 수 있을 것이다.

1-2-2. checkmap? 

두 번째로, 기존에 이동이나 밀기 등을 구현한 코드와는 다르게 checkmap이라는 map과 똑같은 size의 배열이 하나 더 선언되어 있다.

이 맵은 1-1. 그래프 로 비교하자면 그래프에서 방문한 정점을 주황색으로 색칠해주는 기능이라 생각하면 된다.

checkmap의 기능은 방문한 좌표를 기억해서 다시 재방문하지 않도록 하는 기능을 포함하고 있다.

1-2-3. dy? dx?

이동 알고리즘을 구현할 때 사용했던 dy, dx도 다시 등장했다.

1-1. 그래프 에서는 정점의 번호가 낮은 순서대로 DFS했는데, 2차원 맵에서도 DFS를 할 '기준'이 필요하다.

이 코드에서는 dy, dx를 내가 임의로 지정해서 DFS를 할 때 위, 오른쪽, 아래, 왼쪽 순서대로 탐색을 하도록 지시했다.

1-2-4. min_n 

min_n은 출발점부터 도착점까지 최단 경로값을 저장하는 변수이다.

map의 크기가 5x5이므로 가장 멀리 간다해도 25칸보다 작을 것이므로 초기값을 25로 지정했다.

1-3. 결과

이 코드를 실행하면 최종적으로 도착점까지 가는 4가지 경로가 나올 것이다.

도착점에 도달하는 유효한 결과만 본다고 생각했을때,

방향이 위 -> 오른쪽 -> 아래 -> 왼쪽 이니까, 

먼저 다음과 같은 첫 번째 결과 값 12가 나올 것이고,

그 다음으로 결과 값 16,

결과 값 8, 

결과 값 12가 나올 것이다.

전체 코드에서 아래처럼 도착점에 도달할 때 min_n에 cnt(이동 횟수)의 최솟값을 저장하므로

 
if (y == 4 && x == 4) {
        if (min_n > cnt)min_n = cnt;
}
 

결과 값은 8이 나올 것이고,

cout으로 출력하면

8이 출력되는 것을 확인할 수 있다.