[BOJ 25208] 백준 25208번 - 새벽의 탐정 게임
1. 문제Permalink
25208. 새벽의 탐정 게임 (2022 인하대학교 프로그래밍 경진대회(IUPC) D번)
백준 25208번 - 새벽의 탐정 게임 (https://www.acmicpc.net/problem/25208)
2. 풀이Permalink
한 면이 뚫려있다는 조건이 없다면, 최소 이동 횟수를 구하는 평범한 BFS 문제이다. 그런데 이 조건이 추가됨에 따라서, 각 칸 (y, x)에서 뚫려있는 면의 방향에 따라 총 여섯 가지 상태가 추가로 존재하게 된다. 따라서, BFS에서 visited 배열을 3차원으로 만들어주어야 한다. (visited[N][M][6])
D를 시작점으로, R을 도착점으로 하는 BFS를 수행한다. 이때, 현재 뚫려있는 면의 방향과 현재 굴리려는 방향의 두 요소에 따라서, 다음 번에 뚫려있는 면의 방향이 결정된다. 이는 조건문을 사용하거나 배열로 한번에 관리할 수 있다.
종료 조건은 도착한 칸이 R이면서 뚫려있는 면이 바닥일 경우이다. 단, 도착한 칸이 R인데 뚫려있는 면이 바닥이 아니라면, 도둑이 바로 승리를 선언하기 때문에 이 경우는 더이상 BFS가 진행되지 않도록 해야 한다. queue에 해당 node를 집어넣지 않는다는 의미이다.
3. 채점 결과Permalink
4. 회고Permalink
칸이 R이면서 뚫려있는 면이 바닥이 아닌 경우에도 queue에 node를 담아 BFS가 계속되어버리게 구현해서 WA를 받았다.
5. 코드Permalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); | |
| #define FOR(i,a,b) for(int i=(a);i<=(b);i++) | |
| #define ROF(i,a,b) for(int i=(a);i>=(b);i--) | |
| #define ll long long int | |
| #define pii pair<int, int> | |
| #define PQ priority_queue | |
| #define LEN(v) int(v.size()) | |
| #define ALL(v) v.begin(),v.end() | |
| #define INF int(2e9) | |
| #define LINF ll(1e18) | |
| struct NODE { | |
| int y; | |
| int x; | |
| int hole; | |
| }; | |
| int N, M; | |
| char Map[501][501]; | |
| int visited[501][501][6]; | |
| int dy[4] = { -1, 1, 0, 0 }; | |
| int dx[4] = { 0, 0, -1, 1 }; | |
| int dh[4][6] = { {5, 4, 2, 3, 0, 1}, {4, 5, 2, 3, 1, 0}, | |
| {3, 2, 0, 1, 4, 5}, {2, 3, 1, 0, 4, 5} }; | |
| int BFS(int sy, int sx) { | |
| queue<NODE> q; | |
| q.push({ sy, sx, 0 }); | |
| visited[sy][sx][0] = 1; | |
| if (Map[sy][sx] == 'R') { | |
| return 0; | |
| } | |
| while (!q.empty()) { | |
| int y = q.front().y; | |
| int x = q.front().x; | |
| int h = q.front().hole; | |
| q.pop(); | |
| FOR(i, 0, 3) { | |
| int ny = y + dy[i]; | |
| int nx = x + dx[i]; | |
| int nh = dh[i][h]; | |
| if (ny < 1 || nx < 1 || ny > N || nx > M) continue; | |
| if (Map[ny][nx] == '#') continue; | |
| if (Map[ny][nx] == 'R' && nh == 0) { | |
| return visited[y][x][h]; | |
| } | |
| else if (Map[ny][nx] == 'R' && nh != 0) { | |
| continue; | |
| } | |
| if (visited[ny][nx][nh]) continue; | |
| visited[ny][nx][nh] = visited[y][x][h] + 1; | |
| q.push({ ny, nx, nh }); | |
| } | |
| } | |
| return -1; | |
| } | |
| int main() { | |
| FASTIO; | |
| memset(visited, 0, sizeof(visited)); | |
| cin >> N >> M; | |
| int sy = 0, sx = 0; | |
| int ey = 0, ex = 0; | |
| FOR(i, 1, N) { | |
| FOR(j, 1, M) { | |
| cin >> Map[i][j]; | |
| if (Map[i][j] == 'D') { | |
| sy = i, sx = j; | |
| } | |
| } | |
| } | |
| cout << BFS(sy, sx); | |
| return 0; | |
| } |
댓글남기기