[SWEA] 탈주범 검거

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

SW Expert Academy

[풀이]

1) 각 파이프마다 갈 수 있는 방향을 지정해 준다. (상하좌우로 움직이게 하기 전에 미리 설정해둠)

2) 나아가야 할 방향에서 다음 좌표에 위치한 파이프로 갈 수 있는지 판단한 후 지나갈 수 있다면 큐에 넣는다. (check())

3) time == L이면 루프를 중지한다.

 

#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; int n, m, r, c, l; int map[51][51]; typedef pair<int, int> pp; typedef pair<int, pp> ipp; bool visited[51][51]; int dirCnt[8] = {0, 4, 2, 2, 2, 2, 2, 2}; int dirs[8][4] = {{}, {0, 1, 2, 3}, {0, 2}, {1, 3}, {0, 1}, {1, 2}, {2, 3}, {0, 3}}; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //북 동 남 서 int check(int x, int y, int d) { //d방향으로 갔을 때 갈 수 있는 하수구인지 찾기 int noExit = -1; int next = map[x][y]; switch (d) { case 0: if (next == 1 || next == 2) return d; else if (next == 5) return 1; else if (next == 6) return 3; break; case 1: if (next == 1 || next == 3) return d; else if (next == 6) return 2; else if (next == 7) return 0; break; case 2: if (next == 1 || next == 2) return d; else if (next == 4) return 1; else if (next == 7) return 3; break; case 3: if (next == 1 || next == 3) return d; else if (next == 4) return 0; else if (next == 5) return 2; break; default: break; } return noExit; } int bfs(int sx, int sy) { queue<pp> q; // for (int i = 0; i < dirCnt[map[sx][sy]]; i++) // { // q.push(ipp(dirs[map[sx][sy]][i], pp(sx, sy))); // } int cnt = 1; int seq = 1; visited[sx][sy] = true; q.push(pp(sx, sy)); while (!q.empty()) { int size = q.size(); if (seq == l) break; while (size--) { int x = q.front().first; int y = q.front().second; // int d = q.front().first; q.pop(); for (int i = 0; i < dirCnt[map[x][y]]; i++) { int dir = dirs[map[x][y]][i]; int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || !map[nx][ny] || visited[nx][ny]) continue; int n_d = check(nx, ny, dir); if (n_d == -1) { continue; } else { visited[nx][ny] = true; cnt++; q.push(pp(nx, ny)); } } } ++seq; } return cnt; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int tc = 1; tc <= t; tc++) { memset(visited, 0, sizeof(visited)); cin >> n >> m >> r >> c >> l; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } cout << "#" << tc << " " << bfs(r, c) << '\n'; } return 0; }