두더지 굴(S) - 탐색기반 알고리즘 설계 중급 - 깊이우선탐색 기반

1. 소스 코드

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

#include <cstdlib> #include <iostream> #include <ctime> #include <array> #include <vector> #include <algorithm> const unsigned int N = 7; unsigned 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<unsigned 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} }}; std::vector<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 dfs(int y, int x, unsigned int &dist) { map[y][x] = cnt; for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if( (map[ny][nx] == 1) && (isOutOfRange(ny, nx) == false) ) { dist++; dfs(ny, nx, dist); } } } int main() { for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { if(map[y][x] == 1) { cnt++; unsigned int dist = 1; dfs(y, x, dist); vc.push_back(dist); } } } std::cout << "After Scan Tunnel ... "<< std::endl; for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { std::printf("%d ", map[y][x]); } std::printf("\n"); } std::printf("\n"); std::cout << "number of tunnel : " << vc.size() << std::endl; std::sort(vc.begin(), vc.end(), std::greater<int>()); for(auto iter : vc) { std::printf("%d ", iter); } std::printf("\n"); return 0; }

2. 실행 결과

hskim@hskim-VirtualBox:~/share/prj/c++/test2$ ./test After Scan Tunnel ... 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 number of tunnel : 3 9 8 7