1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <stdio.h> #include <queue> #include <utility> #include <string.h> using namespace std; int level, row, col; int st_y, st_x, st_h; int end_y, end_x, end_h; int dh[6] = { 0,0,0,0,1 , -1}; int dx[6] = { 1,-1,0,0,0 ,0}; int dy[6] = { 0,0,1,-1,0 ,0}; char building[40][40][40]; int flag[40][40][40] = { 0 }; // ((y,x), (h, cnt)) queue<pair<pair<int, int>, pair<int,int> > > q; void bfs(); int main() { while (1) { memset(building, 0, sizeof(building)); memset(flag, 0, sizeof(flag)); while (!q.empty()) q.pop(); scanf("%d %d %d", &level, &row, &col); if ((level == 0) && (row == 0) && (col == 0)) break; for (int i = 1; i <= level; i++) { for (int j = 1; j <= row; j++) { char tmp_str[40]; scanf("%s", &tmp_str); for (int k = 1; k <= col; k++) { building[i][j][k] = tmp_str[k - 1]; if (building[i][j][k] == 'S') { st_h = i; st_y = j; st_x = k; } else if (building[i][j][k] == 'E') { end_h = i; end_y = j; end_x = k; } } } } flag[st_h][st_y][st_x] = 1; q.push(make_pair(make_pair(st_y, st_x), make_pair(st_h, 0))); bfs(); } } void bfs() { int rst_cnt = 0; while (!q.empty()) { int cur_cnt = q.front().second.second; int cur_h = q.front().second.first; int cur_y = q.front().first.first; int cur_x = q.front().first.second; q.pop(); if (cur_h <= 0 || cur_h > level) continue; if (cur_y <= 0 || cur_y > row) continue; if (cur_x <= 0 || cur_x > col) continue; if (building[cur_h][cur_y][cur_x] == 'E') { rst_cnt = cur_cnt; break; } for (int i = 0; i < 6; i++) { int hh = cur_h + dh[i]; int xx = cur_x + dx[i]; int yy = cur_y + dy[i]; if ((flag[hh][yy][xx] == 0) && (building[hh][yy][xx] != '#')) { flag[hh][yy][xx] = 1; q.push(make_pair(make_pair(yy, xx), make_pair(hh, cur_cnt+1))); } } } if (rst_cnt == 0) printf("Trapped!\n"); else printf("Escaped in %d minute(s).\n", rst_cnt); } | cs |
이제 DFS, BFS 문제는 자유자재로 풀 수 있는 것 같다
처음으로 3차원 BFS 문제를 풀어봤는데,
매커니즘은 2차원 문제랑 똑같아서 생각보다 할만했다