[BOJ] 3055. 탈출

 

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

3055번: 탈출

이 문제는 물의 이동시간과 고슴도치의 이동시간을 비교해주어야 하기 때문에 둘 다 구해준다.

먼저 물이 차는 시간을 구해 놓고 고슴도치를 이동시키는 것이 편하다.

 

먼저 비버굴의 위치와 고슴도치의 위치를 따로 저장해놓고 물일 때는 바로 큐에 넣어준다.

bfs로 물이 차는 시간을 모두 구했으면 고슴도치의 위치를 시작으로 다시 bfs를 시작한다.

 

고슴도치의 경우 다음과 같이 물이 차는 시간과 비교해주는 부분이 중요하다!

 

처음에

 if(w[nx][ny] == s[x][y]+1) continue;

이렇게 해줬다가 예제는 다 맞는데 틀려서 고민하다가 이미 더 빠른 시간에 차있는 경우가 생각나서

 

 if(w[nx][ny] <= s[x][y]+1) continue;

이렇게 고쳤는데 예제마저 다 틀려버려서 당황했었다.

 

w배열을 방문 확인을 같이 하기 위해 -1로 초기화한 것을 까먹었다ㅠㅠ

최종적으로

 if(w[nx][ny] != -1 && w[nx][ny] <= s[x][y]+1) continue;

이렇게 해주면 완벽하다!

 

마지막으로 비버 굴이 초기값이 아니면(도착시간이 저장되어 있으면) 도착시간을 출력해주고

초기값(-1)이면 KACTUS를 출력해준다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int main() {
    int r,c;
    scanf("%d %d", &r, &c);
 
    char map[50][50];
    int s[50][50];
    int w[50][50];
 
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
 
 
    //이동 시간을 저장해줄 배열을 -1로 초기화
    memset(s,-1,sizeof(s));
    memset(w,-1,sizeof(w));
 
    int dochiX, dochiY;
    int beaverX, beaverY;
 
    queue<pair<int,int> > q;
 
 
    //input
    for(int i=0; i<r; i++) {
      
        for(int j=0; j<c; j++) {
            cin >> map[i][j];
 
            //비버굴 위치
            if(map[i][j] == 'D') {
                beaverX = i;
                beaverY = j;
            } else if(map[i][j] == 'S') {
                //고슴도치 위치
                dochiX = i;
                dochiY = j;
            } else if(map[i][j] == '*') {
                //물인 경우
                q.push(make_pair(i,j));
                w[i][j] = 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 (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            //돌이거나 비버굴인 경우 이동 불가
            if(map[nx][ny] == 'X' || map[nx][ny] == 'D') continue;
            //방문하지 않은 칸이면 방문
            if(w[nx][ny] == -1) {
                q.push(make_pair(nx,ny));
                w[nx][ny] = w[x][y] + 1;
            }
        }
    }
 
    //고슴도치 이동
    q.push(make_pair(dochiX,dochiY));
    s[dochiX][dochiY] = 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 (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
 
            //돌인경우 이동 불가
            if(map[nx][ny] == 'X') continue;
 
            //이동하는 곳에 물이 차는 시간이 고슴도치가 이동하는 시간보다 적은 경우
            //초기값을 위에서 -1 로 해줬으므로 주의 해야한다!!
            if(w[nx][ny] != -1 && w[nx][ny] <= s[x][y]+1) continue;
 
            //방문하지 않은 경우
            if(s[nx][ny] == -1) {
                q.push(make_pair(nx,ny));
                s[nx][ny] = s[x][y] + 1;
            }
 
        }
    }
 
 
    //비버굴에 도착하지 못하는 경우
    if(s[beaverX][beaverY] == -1) {
        cout << "KAKTUS";
    } else { //도착한 경우 도착한 시간을 출력
        cout << s[beaverX][beaverY];
    }
 
    return 0;
}