(C++) - 백준(BOJ) 17836번 : 공주님을 구해라!

https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

bfs문제였습니다.

(첫 글자 대문자 언어 이름 ) - 문제 명 답

 

풀이방법

 문제에서는 (1,1)에서 출발해 (n,m)에 도착하는 최소시간으로 나와있으니 (0,0)에서 출발해 (n-1, m-1)에 도착하는 최소시간으로 생각할 수 있습니다.

 

 1. 입력을 받은 후 bfs를 두 번 수행합니다.

  1-1. 첫 번째 bfs는 (0,0)에서 출발해 그람이 있는 곳으로 가는 최단시간을 구합니다. 그람을 얻은 후에는 맨해튼거리만큼 간다면 바로 공주님에게 갈 수 있으므로 그람까지 가는 최소시간 + n - gram의 행좌표 - 1 + m - gram의 열좌표 - 1가 전체 걸리는 시간입니다.

 

  1-2. 두 번쨰 bfs는 (0,0)에서 출발해 바로 공주님에게 가는 최단시간을 구합니다.

* bfs를 돌며 d배열 변수에 (x,y)로 갈때 최소시간을 저장합니다. 만약 bfs함수의 인자로 받은 도착해야하는 좌표에 해당하는 d의 값이 초기값인 -1이라면 도착하지 못했으므로 아주 큰 값을 반환합니다.

 

2. 1-1과 1-2에서 시행한 결과값중 최소값을 ans변수에 저장합니다. 그 후 t보다 크다면 도착할 수 없으므로 Fail아니라면 ans를 출력합니다.

 

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, m, t, board[101][101], d[101][101];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
struct Coord{ int x, y; } gram;

int bfs(int endX, int endY){
    memset(d,-1,sizeof(d));
    d[0][0] = 0;
    queue <pii> q;
    q.push({0,0});
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= n || 0 > ny || ny >= m) continue;
            if(board[nx][ny] == 1 || d[nx][ny] != -1) continue;
            d[nx][ny] = d[x][y] + 1;
            q.push({nx,ny});
        }
    }
    if(d[endX][endY] == -1) return 0x3f3f3f3f;
    return d[endX][endY];
}

int main(){
    cin >> n >> m >> t;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
            if(board[i][j] == 2) gram = {i,j};
        }
    }
    int ans = min(bfs(gram.x,gram.y) + n - gram.x + m - gram.y - 2 , bfs(n-1,m-1));
    if(ans > t) cout << "Fail";
    else cout << ans;
}