[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) 구현 꿀팁 아닌 꿀팁(?)

깊이 우선 탐색(Depth-First Search) 알고리즘은 완전 탐색(맹목적 탐색)의 일종으로 특정 루트에서 최대한 깊은 루트까지 탐색하고 다시 돌아와 다른 루트를 탐색하는 방식의 알고리즘입니다. 주로 재귀 호출을 통해 구현하며 스택을 사용해 구현할 수도 있습니다. 반복되는 함수 호출이 있기 때문에 메모리 초과를 주의해야 합니다.

개요

사실 DFS(깊이우선탐색), BFS(너비우선탐색), Backtracking(백트래킹)과 같은 기본적인 완전탐색 알고리즘은 학부 수업에서 반드시 가르치는 내용이고 알고리즘 학문에서도 기초적인 수준의 내용이므로 본 포스팅에서는 개념과 이론에 대해서는 생략하겠습니다. 충분한 이론 설명이 필요한 분들께선 서적과 다른 인터넷을 참고해주시면 감사하겠습니다.
본 포스팅에서는 DFS 알고리즘을 빠르게 구현하는 꿀팁 아닌 꿀팁(?)에 대해서 작성하도록 하겠습니다.

꿀팁 같은 꿀팁 아닌 꿀팁인 이유

1. 야매(?), 가라(?) 등과 같은 꿀팁은 아닙니다. 정석적인 DFS 알고리즘의 구현입니다.
2. 알고리즘 구현에 익숙하시고 능수능란한 분들께는 당연한 내용일 수 있습니다.
3. 본 포스팅이 100% 도움된다고 확신할 수 없습니다.
4. DFS 알고리즘을 구현할 때, 구현 코드가 기억이 잘 안나거나 이미지가 잘 떠오르지 않는 분들께 강추드리는 방법입니다. (예전에 필자가 자주 그랬습니다..)
5. 4번과 같은 경험을 가진 분들이 본 포스팅의 내용을 익힌다면 DFS, 백트래킹 알고리즘 구현에 많은 시간 단축이 가능할 것입니다. (필자의 경험이며 모든 분들께 적용하다고는 100% 확신하지 못합니다.)
6. 본 포스팅에서 설명하는 내용은 "삼성 SDS 대학생 알고리즘 특강"의 강사님께서 가르쳐주신 내용이며 문제가 될시 삭제하겠습니다. 해당 강사님께 감사의 말씀을 드리며 저와 같은 분들에게도 작은 도움이 될 수 있을까해서 본 포스팅을 작성하게 되었습니다.

본문

본 본문에서 DFS 알고리즘 구현을 익히는 과정을 번호 순서대로 작성하도록 하겠습니다.

1. 6단계의 구현 과정을 암기합니다.

DFS 알고리즘을 작성하는 단계를 6단계로 나눌 수 있습니다. 아래 6단계를 반드시 반복해서 암기해놓아야 합니다. (더보기를 통해 암기에 활용해보세요!)

1. 체크인
2. 목적지인가
3. 연결된 곳 순회
4. 갈 수 있는가
5. 간다
6. 체크아웃

본 과정은 DFS 구현의 6단계를 암기하는 과정입니다. 따라서 각 단계가 어떤 것을 의미하는지는 아래 구현 과정에서 설명하도록 하겠습니다. 본 과정에서는 위 6단계를 반드시 암기하여 주시기 바랍니다.

2. 구현할 위치에 6단계를 주석으로 적어놓습니다. 

DFS 알고리즘 함수를 구현할 위치에 1번 과정에서 암기한 6단계를 주석으로 적어놓습니다. 그러면 구현 과정에서 별다른 생각과 고민이 적어지며 더 신속하고 빠르게 코드를 작성할 수 있습니다.

void dfs(){
	// 체크인
	// 목적지인가
	// 연결된 곳 순회 
	// 갈 수 있는가 
	// 간다
	// 체크아웃 
}

위와 같은 순서대로 먼저 주석을 작성해 놓으면, 어떠한 완전 깊이 우선 탐색 문제를 해결하더라도 약간의 응용만 있을뿐 거의 위와 같은 순서로 해결할 수 있습니다. (1번 '체크인'과 6번 '체크아웃'의 경우 5번 '간다' 전,후에 위치할 수도 있습니다.)

3. 주석의 내용대로 구현 코드를 작성합니다. (C++ 로 작성)

깊이 우선 탐색을 적용할 수 있는 문제는 보통 그래프 경로 탐색 문제일 수도 있고 주어진 배열의 순열, 조합 탐색 문제에서 활용할 수 있겠습니다. C++ 코드 구현을 통해 예시를 보겠습니다.

예시1 (그래프 탐색)

이차원 그래프로 주워진 퍼즐에서 4개의 칸에 적힌 수의 최대값을 구하는 알고리즘입니다.

int puzzle[MAX][MAX];
bool visit[MAX][MAX];
int dy = {-1, 0, 1, 0};
int dx = {0, 1, 0, -1};

void dfs(int r, int c, int sum, int cnt){
    // 체크인
    visit[r][c] = true; 
    
    // 목적지인가
    if(cnt==4){
    	maxNum = max(maxNum, sum);
        visit[r][c] = false;
        return;
    } 
    // 연결된 곳 순회
    for(int i=0; i<4; i++){
    	int ty = r + dy[i];
        int tx = c + dx[i];
		
        // 갈 수 있는가
        if( !visit[ty][tx] && 0 <= ty && ty < N && 0 <= tx && tx < M ){
			// 간다
            dfs(ty, tx, sum+puzzle[ty][tx], cnt+1);
        }
    }
    // 체크아웃
    visit[r][c] = false;
}

1. 체크인 과정은 방문을 했다고 체크하는 과정입니다. 불필요한 반복과 무한루프를 방지할 수 있습니다.
2. 목적지인가 확인하는 과정은 문제와 조건에 따라 많이 다를 수 있습니다. 위 예시에서는 퍼즐 4개의 칸의 합을 구하는 문제였기 때문에 4번에 도달하는 조건이 목적지라고 할 수 있습니다. 따라서 cnt 값이 4가 되면 탐색을 종료하고 반환합니다. 보통 목적지 칸에 도달했는지로 체크하는 경우가 많습니다. (조건에 따라 최대값을 구하거나 해를 도출하는 과정이 필요할 수 있습니다. 또한 위 예시에서는 아래 체크아웃 과정이 생략되기 때문에 반환 전에 체크아웃을 해주었습니다.)
3. 연결된 곳을 순회하는 과정 또한 문제에 따라 다른데, 위 예시와 같이 가장 흔하게 쓰이는 이차원 그래프 탐색의 경우에는 y축과 x축의 이동방향으로 순회하는 방식으로 구현합니다. 위 예시는 시계 방향(위, 우, 아래, 좌)으로 순회하는 것을 구현한 코드입니다. 보통 방향을 설정한 배열로 자료구조를 구축하고 그 배열을 순회하여 다음 타겟에 더하는 방식으로 구현합니다. 만약 한칸이 아닌 경우에는 원하는 칸만큼 곱하는 방식으로 구현할 수 있겠습니다.
4. 갈 수 있는가 확인하는 과정은 다음에 탐색할 타겟 위치가 이미 방문한 곳이 아닌지, 정해진 범위에서 벗어나지 않았는지 체크하는 과정이라 할 수 있습니다. 위의 예시에서는 방문체크와 함께 퍼즐의 범위를 벗어나는지를 확인합니다. 이 외에도 문제 조건의 따라 갈 수 있는지 없는지에 대한 조건을 추가로 구현할 수 있습니다.
5. 간다 과정은 DFS 함수의 재귀호출을 통해 다음 타겟으로 진행하는 과정입니다. 매개변수에 적절한 값을 넘겨주어 다음 과정을 반복하게 합니다. 여기서 재귀 호출의 논리를 잘 생각해야합니다. 재귀 함수가 호출된 순간 아래에 작성된 코드보다 재귀로 호출된 함수가 먼저 수행될 것입니다. 따라서 재귀적으로 호출된 함수들은 목적지에 다다르기까지 깊이를 우선하여 탐색할 것입니다.
6. 체크아웃 과정은 이제 탐색을 마치고 작업 수행이 끝난 곳을 다시 돌려놓는 과정입니다. 어느 한 루트의 깊이 우선 탐색으로 찾은 위치를 다른 루투의 깊이 우선 탐색으로도 찾을 수 있게 하기 위함입니다. 재귀 호출 부분의 아래부분에 작성되었기 때문에 가장 마지막에 호출된 함수부터 차례대로 체크아웃이 수행됩니다.

예시2 (순열 탐색)

nums라고 주어진 배열에 있는 값들로 만들 수 있는 6개의 오름차순 순열을 모두 출력하는 알고리즘입니다. 아래 예시에서는 1번 '체크인' 과정과 6번 '체크아웃' 과정이 5번 '간다' 전,후에 위치해서 구현하였습니다.

int nums[MAX];
vector<int> ans;
bool visit[MAX];

void dfs(int idx){
    // 목적지인가
    if(ans.size()==6){
    	for(int i=0; i<6; i++){
        	cout << ans[i] << " ";
        }
        cout << "\n";
        return;
    }
    
    // 연결된 곳 순회
    for(int i=idx; i<k; i++){
    	// 갈 수 있는가 
        if(!visit[i]){
            // 체크인
            visit[i] = true;
            ans.push_back(nums[i]);
            
            // 간다
            dfs(i);
            
            // 체크아웃
            ans.pop_back();
            visit[i] = false;
        }
    }
}

1. 목적지인가 과정에서 구한 순열의 길이가 6인지 확인하여 맞는 경우에 출력하고 탐색을 종료합니다.
2. 연결된 곳을 순회하는 과정에서는 오름차순으로 정렬된 배열을 오름차순 순열로 출력하기 위함이므로 현재 위치의 배열 인덱스로 부터 뒤의 인덱스를 모두 순회합니다.
3. 갈 수 있는가 확인하는 과정은 위 예시에서는 단순히 방문했는지 안했는지만 체크하면 되겠습니다.
4. 체크인 과정이 위 예시에서는 여기서 진행합니다. '간다' 과정 전에 진행함으로서 타겟 위치를 체크인합니다. 체크인 과정을 여기서 진행하면 따로 매개변수로 다음 위치값을 넘기지 않아도 된다는 장점이 있습니다. (위 예시에서는 순열 리스트(벡터)에 값을 추가하는 과정도 있습니다.)
5. 간다 과정은 역시 DFS 재귀 함수를 호출하는 것입니다. 필요한 매개변수를 넘겨주면 되겠습니다.
6. 체크아웃 과정은 여기서는 함수 호출이 끝난 후에 바로 수행함으로써 원래대로 돌려놓는 과정입니다. 순열 리스트(벡터)에 넣었던 값을 다시 빼고 방문 체크도 해제합니다. 이처럼 체크인/체크아웃 과정을 DFS 함수 호출 전,후에 배치하게 되면 대칭적으로 수행해야하는 과정을 한눈에 알아보기 쉽게 처리할 수 있습니다. 따라서 저는 백트래킹으로 탐색해야하는 알고리즘의 경우 보통 이처럼 구현합니다. 

예시3 (인접 리스트 탐색)

아래 예시는 인접 리스트로 구현된 그래프에서 5번의 이동이 이뤄지면 탐색을 종료하는 알고리즘입니다.

vector<int> adj[MAX];
bool visit[MAX];

void dfs(int v, int cnt){
    // 체크인
    visit[v] = true;
    
    // 목적지인가
    if(cnt==5){
    	cout << 1 << "\n";
        exit(0);
    }
    
    // 연결된 곳 순회
    for(int i=0; i<adj[v].size(); i++){
    	// 갈 수 있는가
        if(!visit[adj[v][i]]){
        
            // 간다
            dfs(adj[v][i], cnt+1);
        }
    }
    
    // 체크아웃
    visit[v] = false;
}

1. 체크인 과정에서 방문했다고 기록합니다.
2. 목적지인가 과정에서 5번의 탐색을 했는지 확인하고 맞는 경우 1을 출력하고 프로그램을 종료합니다.
3. 연결된 곳을 순회하는 과정에서는 예시1의 그래프와 다르게 현재 노드와 인접한 리스트들을 순회하게 됩니다. 따라서 현재 노드가 인접하고 있는 노드들을 순회한다고 할 수 있습니다. 
4. 갈 수 있는가 확인하는 과정에서는 역시 방문했는지 안했는지 확인합니다.
5. 간다 과정에서 다음 노드를 매개변수로 넘겨주며, 길이를 늘려줍니다.
6. 체크아웃 과정은 방문이 끝났다고 기록해주면 되겠습니다.

정리

완전 탐색 알고리즘은 그 이름에 맞게 확인할 수 있는 모든 경우와 경로를 탐색하는 알고리즘을 뜻합니다. 따라서 수행시간을 단축하기보다는 어떻게 모든 것을 탐색할 수 있을까에 대한 해결 과정입니다.
깊이를 우선적으로 탐색하는 문제의 경우 위의 6가지 과정으로 DFS 알고리즘을 구현한다면 조건 설정만 다를 뿐 거의 대부분의 문제를 해결할 수 있습니다.  

결론

본 포스팅에서는 DFS 알고리즘을 작성할 때, 많은 생각없이 효율적으로 빠르게 구현할 수 있도록 도움을 드리고자 작성하였습니다. 실제로 저도 이 방식을 배운 이후로 많은 시간 단축이 있었고 완전 탐색에 대한 자신감도 가질 수 있게 되었습니다. 모든 분들이 이 방식이 도움된다고 확신할 수 없지만 많은 분들에게 조금이나마 가치가 될만한 포스팅이 되었으면 합니다.
앞서 적었듯이 본 방식은 제가 만든 방식이 아닌 다른 강사님께 배운 방식이며 문제가 될 시 삭제하겠습니다. 의견남겨주시기 바랍니다.
또한 더 다양한 완전 탐색 알고리즘 문제를 해결해보면서 보완하거나 추가해야할 사항이 생기면 수정하겠습니다. 추가 의견이나 피드백 주시면 감사하겠습니다.

너비 우선 탐색(BFS, Breadth-First Search) 알고리즘 포스팅은 다음 링크에서 확인할 수 있습니다.
https://devluce.tistory.com/17

[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 구현 꿀팁 아닌 꿀팁(?)