boj 17836 공주님을 구해라!

www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

시작점 : (1, 1)

도착점 : (N, M)

제한 시간 : T

무기가 없으면 벽을 지나갈 수 없지만 무기가 있으면 모든 벽을 부수고 지나갈 수 있습니다.

visit[x][y][chk] : x, y에 도달했을 때 무기를 가진 상태로 방문했는지 여부

 

1. 다음 칸이 무기가 있는 칸일 경우(list[nx][ny] = 2)

- 무기를 획득하였으므로 chk=true인 값을 큐에 넣어줍니다.

2. 다음 칸이 벽이 아니고 방문하지 않았을 경우

- 평상시 bfs처럼 다음 정점을 큐에 넣고 방문체크합니다.

3. 다음 칸이 벽이고 무기를 가진 상태인 경우

- 무기를 갖고있으면 어디든 지나갈 수 있으므로 2번과 같은 로직을 수행합니다.

 

도착지점인 (N, M)의 값은 0이므로 2, 3번에서 (N, M)에 도달하였으면 현재 시간을 출력합니다.

만약 T시간 동안 (N, M)에 도달하지 못하면 Fail을 출력합니다.

 

 

#include <iostream>
#include <queue>
using namespace std;
 
typedef struct Point {
    int x;
    int y;
    bool chk;
};
 
queue<Point> q;
bool visit[101][101][2];
int list[101][101];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, T;
 
void bfs() {
    q.push({ 1,1,false });
    visit[1][1][0] = true;
    for (int t = 1; t <= T; t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().x;
            int y = q.front().y;
            bool chk = q.front().chk;
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
                if (list[nx][ny] == 2 && !visit[nx][ny][1]) {
                    q.push({ nx,ny,true });
                    visit[nx][ny][1] = true;
                }
                else if (list[nx][ny] == 0 && !visit[nx][ny][chk]) {
                    q.push({ nx,ny,chk });
                    visit[nx][ny][chk] = true;
                    if (nx == N && ny == M) {
                        cout << t << '\n';
                        return;
                    }
                }
                else if (list[nx][ny] == 1 && chk && !visit[nx][ny][chk]) {
                    q.push({ nx,ny,chk });
                    visit[nx][ny][chk] = true;
                    if (nx == N && ny == M) {
                        cout << t << '\n';
                        return;
                    }
                }
            }
        }
    }
 
    cout << "Fail\n";
}
 
void input() {
    cin >> N >> M >> T;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    bfs();
 
    return 0;
}