(C++) - 백준(BOJ) 3055번 : 탈출

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

3055번: 탈출

bfs 구현문제였습니다

 

풀이방법

 1. '*'들 즉 물이 있는 위치를 행,열 형태로 queue에 저장합니다.

 

 2. bfs를 통해 물이 어떤 특정 타일에 도착하는 거리들을 모두 구합니다.

 

 3. bfs를 통해 고슴도치가 특정 타일에 도착하는 거리들을 모두 구합니다.

 

 4. 'D'의 위치에서 인접한 상하좌우칸을 확인하며 탈출 가능여부를 판단합니다.

   4-1. 탈출 경로가 존재하고 물보다 빨리 'D'의 인접칸에 도착할 수 있다면 ans를 최솟값으로 갱신합니다.

   4-2. 물이 도착할 수 없는 지점이지만 고슴도치가 'D'인접칸에 도착했을 때도 ans가 갱신됩니다.

   4-3. 고슴도치가 바로 탈출할 수 있는 경우에는 ans가 1입니다.

 

5. 갱신이 되지 않아 ans가 초기값 0x3f3f3f3f이라면 "KAKTUS"를 출력합니다. 그 외에는 최솟값이 저장된 ans를 출력합니다.

 

* char형 변수로 입력을 받을경우 마지막에 null문자가 들어가는 것을 의식해야합니다. 50칸을 입력받았을 때 51칸을 선언해줘야 50글자를 입력받을 수 있습니다.

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int r,c,sr,sc, escapeR, escapeC;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
char board[51][51];
int waterDist[51][51], beaverDist[51][51];
queue <pii> waterQ;

void waterBFS(){
    queue <pii> q;
    while(!waterQ.empty()) {
        int x = waterQ.front().first;
        int y = waterQ.front().second;
        q.push({x,y});
        waterDist[x][y] = 0;
        waterQ.pop();
    }

    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 >= r || 0 > ny || ny >= c) continue;
            if(board[nx][ny] == 'X' || board[nx][ny] == 'D' || waterDist[nx][ny] != -1) continue;
            waterDist[nx][ny] = waterDist[x][y] + 1;
            q.push({nx,ny});
        }
    }
}

void beaverBFS(){
    queue <pii> q;
    q.push({sr,sc});
    beaverDist[sr][sc] = 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 >= r || 0 > ny || ny >= c) continue;
            if(board[nx][ny] == 'X' || board[nx][ny] == 'D' || beaverDist[nx][ny] != -1) continue;
            beaverDist[nx][ny] = beaverDist[x][y] + 1;
            q.push({nx,ny});
        }
    }
}

int getAns(){
    int ans = 0x3f3f3f3f;
    for(int i = 0; i < 4; i++){
        int nx = escapeR + dx[i];
        int ny = escapeC + dy[i];
        if(0 > nx || nx >= r || 0 > ny || ny >= c) continue;
        if(waterDist[nx][ny] > 0 && beaverDist[nx][ny] >= waterDist[nx][ny]) continue;
        if(beaverDist[nx][ny] == -1) continue;
        ans = min(ans,beaverDist[nx][ny] + 1);
    }
    return ans == 0x3f3f3f3f ? -1 : ans;
}

int main(){
    memset(waterDist,-1,sizeof(waterDist));
    memset(beaverDist,-1,sizeof(beaverDist));
    cin >> r >> c;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> board[i][j];
            if(board[i][j] == 'S') sr = i, sc = j;
            else if(board[i][j] == 'D') escapeR = i, escapeC = j;
            else if(board[i][j] == '*') waterQ.push({i,j});
        }
    }

    waterBFS();
    beaverBFS();

    int ans = getAns();

    if(ans == -1) cout << "KAKTUS";
    else cout << ans;
}

 

Test Case

질문게시판에 있는 반례들을 모아봤습니다.

 

input

50 50

..................................................

............................................XXXXD.

...............................................XXX

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

................................S.................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..............................................*...

..................................................

..................................................

..................................................

답 : 44

 

input

3 3
.XS
*..
.D.
답 : 3

 

input
3 3
.*.
D.X
..S
답 : 3

 

input
3 3
.D.
..*
SX.
답 : 3

 

input
3 3
S..
X.D
.*.

답 : 3

 

input

3 3

S..

.D.

...

답 : 2

 

input

2 2

SD

**

답 1