너비우선탐색 기반 최단 거리 예제 풀이

1. 목적

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

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

2. 코드 설명

너비 우선 탐색 기반은 비선형 탐색의 한 종류로 Queue 기반으로 Stack 기반의 깊이기반 탐색에서 10만번 이상을 수행 시에 Stack Overflow에 대한 제약 사항을 해결할 수 있는 하나의 방식이다.

#include <iostream> #include <array> #include <queue> 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<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} }}; using coordinate = struct { int x; int y; unsigned int l; }; bool isOutOfRange(int x, int y) { if( (x < 0) || (x > N-1) ) { //std::printf("out of range x \n"); return true; } if( (y < 0) || (y > N-1) ) { //std::printf("out of range y \n"); return true; } return false; } void bfs(int x, int y) { std::queue<coordinate> q; q.push(coordinate{x, y, 0}); // 기존에 방문한 좌표를 재 방문하는 것을 막기 위해서 처리, 보통 visited라는 새로운 배열을 쓰곤한다. map[y][x] = -1; while(!q.empty()) { coordinate pos = q.front(); q.pop(); if( (pos.x == N-1) && (pos.y == N-1) ) { if(min > pos.l) { min = pos.l; std::printf("end of map : min = %u \n", min); } } for(int i = 0; i < 4; i++) { int nx = pos.x + dx[i]; int ny = pos.y + dy[i]; unsigned int nl = pos.l; if( (isOutOfRange(nx, ny) == false) && (map[ny][nx] == 1) ) { // 기존에 방문한 좌표를 재 방문하는 것을 막기 위해서 처리, 보통 visited라는 새로운 배열을 쓰곤한다. map[ny][nx] = -1; q.push(coordinate{nx, ny, nl+1}); } } } } int main() { bfs(0, 0); for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { std::printf("%2d ", map[y][x]); } std::printf("\n"); } std::printf("\n최단거리 : %u \n", min); return 0; }

3. 실행 결과

깊이 우선 순위 탐색과 달리 Path가 나눠져서 도달하지는 않는다.

end of map : min = 12 
-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 

최단거리 : 12