미로 찾기 예제 풀이

1. 소스 코드

문제해결을 위한 창의적 알고리즘(중급), 100페이지 4문제로 미로가 주워지고 'S'에서 출발해서 'G'로 끝나점까지의 최단 거리를 찾는 문제이다. 기존에 두더지 문제를 잘 풀었다면 어렵지 않게 해결할 수 있다.

문제 해결은 깊이 우선 또는 너비 우선 순위로 해결할 수 있지만 너비 우선 순위로 풀어 보았다.

#include <iostream> #include <array> #include <algorithm> #include <queue> const int N = 5; std::array<int, 4> dx = {-1, 0, 1, 0}; std::array<int, 4> dy = {0, -1, 0, 1}; std::array<std::array<char, N>, N> map = {{ {'#', 'S', '#', '#', '#'}, {'#', '.', '.', '.', '#'}, {'#', '.', '#', '.', '#'}, {'#', '.', '.', '.', '.'}, {'#', '#', '#', 'G', '#'} }}; using coordinate = struct _coordinate { int x; int y; int l; }; bool isOutOfRange(int y, int x) { if( (x < 0) || (x > N-1) ) { return true; } if( (y < 0) || (y > N-1) ) { return true; } return false; } int bfs(int y, int x, int dist) { std::queue<coordinate> q; q.push(coordinate{x, y, dist}); while(!q.empty()) { coordinate pos = q.front(); q.pop(); if(map[pos.y][pos.x] == 'G') { std::printf("find road : %d \n", pos.l); return pos.l; } for(int i = 0; i < 4; i++) { int nx = pos.x + dx[i]; int ny = pos.y + dy[i]; int nl = pos.l + 1; if( (isOutOfRange(ny, nx) == false) && ((map[ny][nx] == '.') || (map[ny][nx] == 'G')) ) { if(map[ny][nx] == '.') map[ny][nx] = '-'; q.push(coordinate{nx, ny, nl}); } } } return -1; } int main() { int min = -1; for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { if(map[y][x] == 'S') { min = bfs(y, x, 0); } } } std::printf("\n"); for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { std::printf("%c ", map[y][x]); } std::printf("\n"); } std::printf("\n"); std::printf("최단 거리 : %d \n", min); return 0; }

2. 실행 결과

find road : 6 

# S # # # 
# - - - # 
# - # - # 
# - - - - 
# # # G # 

최단 거리 : 6