깊이우선 탐색(depth first search) 기반 최단 거리 예제 풀이

1. 목적

공부한 내용 다음에 다시 복습하기 위해서 여기에 정리. 알고리즘 동작 원리는 설명은 생략.

여기 (http://blog.eairship.kr/268) 블로그에 정리된 내용 중에 최단 거리 탐색 문제를 내 나름되로 짜 봤다.

2. 코드 설명

깊이 우선 탐색 기반은 Stack 기반이고, 기존에 방문한 Node에 대해서 원하는 답을 얻지 못할 경우 다시 현재 Node 전의 Node로 이동해야 하는데 이 때 현재 Node 탐색에 사용된 중간 결과는 모두 원래되로 돌려줘야 한다. Back Tracking 기반이라는 의미로 해석된다. 흔히 운영체제나 이런 곳에서 Stack 되감기 이런 말을 들을 수 있는데 이 문제에서 많은 영감을 얻을 수 있다.

#include <iostream> #include <array> const int N = 5; unsigned int min = 0xFFFFFFFF; std::array<int, 4> dx = {-1, 0, 1, 0}; std::array<int, 4> dy = {0, -1, 0, 1}; std::array<std::array<bool, N>, N> visited; std::array<std::array<int, N>, N> map = {{ {1, 1, 1, 1, 1}, {0, 0, 0, 0, 1}, {1, 1, 1, 1, 1}, {1, 0, 1, 0, 0}, {1, 1, 1, 1, 1} }}; bool isOutOfRange(int y, int x) { if( (x < 0) || (x > N-1) ) { return true; } if( (y < 0) || (y > N-1) ) { return true; } return false; } void dfs(int x, int y, unsigned int distance) { if(isOutOfRange(y, x) == true) { return; } if( map[y][x] == 0) { //std::printf("no road \n"); return; } if( visited[y][x] == true) { //std::printf("already visited \n"); return; } if( (x == N-1) && (y == N-1) ) { if(min > distance) { min = distance; std::printf("end of loop .. distance : %d \n", distance); return; } } for(int i = 0; i < 4; i++) { visited[y][x] = true; // for backtracking of depth first search dfs(x + dx[i], y + dy[i], distance+1); visited[y][x] = false; // for backtracking of depth first search } } int main() { dfs(0, 0, 0); std::printf("\n최단거리 : %u \n", min); return 0; }

3. 실행 결과

결론적으로 두 가지 Path로 종점에 도달하였고, 그 중 최소값을 선택하는 문제이다.

end of loop .. distance : 16 
end of loop .. distance : 12 

최단거리 : 12