[BaekJoon 3055번] 탈출(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

3055번: 탈출

 

 

[문제 설명]

 

 

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

 

 

[입력]

 

 

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

 

 

[출력]

 

 

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

 

 

[입출력 예]

 

 

입력	출력
3 3 D.* ... .S.	3
3 3 D.* ... ..S	KAKTUS
3 6 D...*. .X.X.. ....S.	6
5 4 .D.* .... ..X. S.*. ....	4

 

 

[문제 풀이]

 

쉬운 문제였고, 문제를 풀다보니깐 백준 5427번 불과 유사한 문제라고 느꼈다.

[BaekJoon 3055번] 탈출(C++)

 

 

물과 고슴도치에 대한 BFS 를 구하고

마지막에 

비버 굴의 위치일 때 -1(초기값)이 아닌 경우 시간을 출력해주었다.

비버 굴의 위치일 때 -1(초기값 그대로)인 경우 이동할 수 없었으므로 "KAKTUS"를 출력해주었다.

if(hedgehog_time[beaverX][beaverY] != -1) {
        cout << hedgehog_time[beaverX][beaverY];
    } else {
        cout << "KAKTUS";
}

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

string board[51];

int hedgehog_time[51][51];
int water_time[51][51];

int dx[4] = {1, 0, -1 , 0};
int dy[4] = {0, 1, 0, -1};

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int R, C;
    cin >> R >> C;
    queue<pair<int, int>> hedgehog;
    queue<pair<int, int>> water;

    int beaverX = 0; int beaverY = 0;
    for(int i = 0; i < R; ++i) {
        cin >> board[i];
        fill(hedgehog_time[i], hedgehog_time[i] + C, -1);
        fill(water_time[i], water_time[i] + C, -1);
        for(int j = 0; j < C; ++j) {
            if(board[i][j] == 'S') {
                hedgehog.push({i,j});
                hedgehog_time[i][j] = 0;
            } else if(board[i][j] == '*') {
                water.push({i,j});
                water_time[i][j] = 0;
            } else if(board[i][j] == 'D') {
                beaverX = i;
                beaverY = j;
            } else {}
        }
    }

    // 물 시간 구하기
    while(!water.empty()) {
        pair<int, int> cur = water.front();
        water.pop();
        for(int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if((board[nx][ny] == 'X') || (water_time[nx][ny] != -1)) continue;
            if ((nx == beaverX) && (ny == beaverY)) continue;
            water.push({nx,ny});
            water_time[nx][ny] = water_time[cur.first][cur.second] + 1;
        }
    }

    // 고슴 도치 시간 구하기
    bool issuccess = false;
    while(!hedgehog.empty()) {
        pair<int, int> cur = hedgehog.front();
        hedgehog.pop();
        for(int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if((board[nx][ny] == 'X') || (hedgehog_time[nx][ny] != -1)) continue;
            if((water_time[nx][ny] != -1) && (water_time[nx][ny] <= hedgehog_time[cur.first][cur.second] + 1)) continue;
            hedgehog.push({nx, ny});
            hedgehog_time[nx][ny] = hedgehog_time[cur.first][cur.second] + 1;
        }
    }

    if(hedgehog_time[beaverX][beaverY] != -1) {
        cout << hedgehog_time[beaverX][beaverY];
    } else {
        cout << "KAKTUS";
    }
    return 0;
}