두더지 굴 탐색 예제 - 너비 우선 탐색 기반 (BFS)

1. 소스 코드

문제해결을 위한 창의적 알고리즘(중급), 77페이지 문제에 있는 문제로 두더지 굴이 몇 개 있으며, 각 두더지 굴의 깊이를 출력하는 문제이다.

#include <iostream> #include <array> #include <queue> const int N = 7; int cnt = 1; 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 = {{ {0, 1, 1, 0, 1, 0, 0}, {0, 1, 1, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1, 0}, {0, 1, 1, 1, 0, 0, 0} }}; using coordinate = struct { int x; int y; }; std::vector<unsigned int> vc; 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 bfs(int y, int x, unsigned int &dist) { std::queue<coordinate> q; q.push(coordinate{x, y}); map[y][x] = cnt; while(!q.empty()) { dist++; coordinate pos = q.front(); q.pop(); for(int i = 0; i < 4; i++) { int nx = pos.x + dx[i]; int ny = pos.y + dy[i]; if( (map[ny][nx] == 1) && (isOutOfRange(nx, ny) == false) ) { map[ny][nx] = cnt; q.push(coordinate{nx, ny}); } } } } int main() { for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { if(map[y][x] == 1) { unsigned int dist = 0; cnt++; bfs(y, x, dist); vc.push_back(dist); } } } 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"); std::cout << "두더지 굴 개수 : " << vc.size() << std::endl; for(auto iter : vc) { std::printf("%d ", iter); } std::printf("\n"); return 0; }

2. 실행 결과

 0  2  2  0  3  0  0 
 0  2  2  0  3  0  3 
 2  2  2  0  3  0  3 
 0  0  0  0  3  3  3 
 0  4  0  0  0  0  0 
 0  4  4  4  4  4  0 
 0  4  4  4  0  0  0 

두더지 굴 개수 : 3
7 8 9