[Baekjoon] 백준 3055번 탈출

3055번 탈출 문제 풀이

문제

• 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
  티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
  매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
  티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
  고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

입력

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

출력

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

예제

입력
3 3
D.*
...
.S.

3 3
D.*
...
..S

3 6
D...*.
.X.X..
....S.


5 4
.D.*
....
..X.
S.*.
....

출력
3 
KAKTUS
6
4

코드

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<tuple>
#include<cstring>
#pragma warning(disable:4996)
using namespace std;

int n, m;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
char map[51][51];
int water[51][51];
int d[51][51];
int startx;
int starty;
int destinationx;
int destinationy;
int waterx;
int watery;
queue<pair<int, int>> q;

void water_bfs() {
    int x, y;
    while (!q.empty()) {
        tie(x, y) = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
            if (map[nx][ny] == '.' && water[nx][ny] == -1 ) {
                water[nx][ny] = water[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
}

void bfs() {
    int x, y;
    while (!q.empty()) {
        tie(x, y) = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
            if (d[nx][ny] != -1) continue;
            if (map[nx][ny] == 'X') continue;
            if (d[x][y] + 1 >= water[nx][ny] && water[nx][ny] != -1) continue;
            d[nx][ny] = d[x][y] + 1;
            q.push(make_pair(nx, ny));
        }
    }
}

int main() {
    cin >> n >> m;
    memset(d, -1, sizeof(d));
    memset(water, -1, sizeof(water));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == '*') {
                q.push(make_pair(i, j));
                water[i][j] = 0;
            }
            if (map[i][j] == 'S') {
                startx = i;
                starty = j;
                d[i][j] = 0;
            }
            if (map[i][j] == 'D') {
                destinationx = i;
                destinationy = j;
            }
        }
    }
    water_bfs();
    q.push(make_pair(startx, starty));
    bfs();
    if (d[destinationx][destinationy] == -1) {
        cout << "KAKTUS" << "\n";
    }
    else {
        cout << d[destinationx][destinationy] << "\n";
    }

}

해결방법

• 다음에 물이 찰 예정이거나, 이미 물이 차있는 공간은 진입할 수 없다. 따라서 물이 차는 시간을 저장해 놓는 water[][]배열과 이동거리를 저장한 d[][]배열을 비교하여 결과를 도출한다.

    void water_bfs() {
        int x, y;
        while (!q.empty()) {
            tie(x, y) = q.front(); q.pop();
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
                if (map[nx][ny] == '.' && water[nx][ny] == -1 ) {
                    water[nx][ny] = water[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }

• main에서 지도를 입력할 때 '*'위치를 미리 queue에 저장시켜놓았다. 이 때 물이 찬 부분이 무조건 한 곳이라는 조건이 없기 때문에 물이 찬 모든 부분을 queue에 넣어준 후 시작해야한다.

    void bfs() {
        int x, y;
        while (!q.empty()) {
            tie(x, y) = q.front(); q.pop();
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
                if (d[nx][ny] != -1) continue;
                if (map[nx][ny] == 'X') continue;
                if (d[x][y] + 1 >= water[nx][ny] && water[nx][ny] != -1) continue;
                d[nx][ny] = d[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }

• 이동거리를 저장시키는 bfs이다. 실제 문제를 해결하며 가장 실수를 많이한 부분이다. map[][]에서 '.'표시로 된 부분만 지나갈 수 있으며, 물이 차있거나, 찰 예정인 부분은 지나갈 수 없다. 즉 d[x][y]+1이 water[nx][ny]보다 작거나, water[nx][ny]가 -1인 경우에만 지나갈 수 있다.

• 실제 풀이하며 나왔던 오류는 메모리 초과 오류이다. if (d[nx][ny] != -1) continue; 이미 지나온 경로를 다시 탐색하지 않도록 해야하지 않아서 계속 메모리에 쌓여 메모리 초과 요류가 발생했었다.