[BOJ/17836번공주님을구해라!] c++ / BFS

문제

(1, 1)칸에서 (N, M)까지 가는데 걸리는 최소 시간을 구하는 문제

-벽은 통과할 수 없음

-그람을 얻을 경우, 개수 제한 없이 벽을 통과할 수 있음

-제한 시간 내에 도착하지 못할 경우 Fail을 출력

 

생각

방문 배열을 2개 만들어서 그람을 획득 했을 때와 하지 못했을 때의 거리를 구하면 되겠다 생각함

 

문제풀이

1.그람이 있는 위치 Gx, Gy에 저장

2.( 1, 1 )방문표시 + 큐에 푸쉬 : BFS 탐색 시작

3.G = 0이면, 벽은 통과할 수 없음 

3-1.방문표시 없는 빈 공간이 나오면, 큐에 푸쉬 + 방문표시

3-2.만약 Gx, Gy가 나오면, vis[Gx][Gy][1] 에는 vis[Gx][Gy][0] + 1 값을 대입해줘야 함( 획득 이전까지 이동한 거리는 동일하기 때문 )

4.G = 1이면, 벽을 통과할 수 있음

4-1.방문하지 않은 곳이 나오면, 큐에 푸쉬 + 방문표시

5.(N, M)에 도착하면 vis[N][M][G] 반환 ( 둘중 뭐가 더 빠를지 모름 / 반환 빨리 되는게 더 빠른 것임 )

6.T 이내에 도착했다면, 반환값 출력

6-1.그렇지 않다면, Fail 출력

 

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
int board[101][101];
int vis[101][101][2]; // 그람 획득 전, 획득 후 방문표시
int N, M, T, cnt=0;
int Gx, Gy, result=0;
int BFS() {
    queue<tuple<int, int, int>> Q;
    memset(vis, -1, sizeof(vis));
    vis[1][1][0] = 0;
    vis[1][1][1] = 0;
    Q.push({1, 1, 0});

    while(!Q.empty()) {
        int x = get<0>(Q.front());
        int y = get<1>(Q.front());
        int G = get<2>(Q.front());
        Q.pop();

        if ( x == N && y == M ) 
            return vis[x][y][G];

        for ( int dir = 0; dir < 4; dir++ ) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if ( nx < 1 ||  nx > N || ny < 1 || ny > M ) continue;
            
            if ( board[nx][ny] != 1 && vis[nx][ny][0] == -1 && G == 0 ) {
                vis[nx][ny][0] = vis[x][y][0] + 1; 
                
                if ( nx == Gx && ny == Gy ) {
                    vis[nx][ny][1] = vis[x][y][0] + 1; 
                    Q.push({nx, ny, 1});
                }
                else 
                    Q.push({nx, ny, 0});
            }   

            if ( vis[nx][ny][1] == -1 && G == 1 ) {
                vis[nx][ny][1] = vis[x][y][1] + 1;
                Q.push({nx, ny, 1});
            }
        }
    }
    return -1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> T;
    for ( int i = 1; i <= N; i++ )
        for ( int j = 1; j <= M; j++ ) {
            cin >> board[i][j];
            if ( board[i][j] == 2 )
                Gx = i, Gy = j;
        }
    
    result = BFS();

    if ( result == -1 || result > T ) 
        cout << "Fail";
    else 
        cout << BFS(); 
}