[백준] 3055번 : 탈출 (C++)

3055번 : 탈출

---

문제)

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

 

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

 

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

 

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

 

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

 

 

 

입력 :

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

// 3055. 탈출
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n, m;
vector<vector<char>> vec;
 
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
 
// bfs에 활용할 queue
queue<pair<int, int>> q;
 
// 고슴도치의 시작 위치
pair<int, int> start;
 
int bfs()
{
    vector<vector<int>> visited;
    visited.resize(n, vector<int>(m, 0));
    visited[start.first][start.second] = 1;
 
    // 고슴도치가 가장 마지막에 움직이므로,
    q.push(start);
 
    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 || nx >= n) continue;
            if (ny < 0 || ny >= m) continue;
            if (vec[nx][ny] == 'X') continue;
            if (visited[nx][ny]) continue;
 
            // 지금 움직이는게 고슴도치이고, 다음 도착지가 비버의 굴이라면
            if (vec[x][y] == 'S' && vec[nx][ny] == 'D')
            {
                return visited[x][y];
            }
 
            // 물이 움직인다.
            if (vec[x][y] == '*')
            {
                if (vec[nx][ny] == '*' || vec[nx][ny] == 'D') continue;
                vec[nx][ny] = '*';
                q.push(make_pair(nx, ny));
            }
            // 고슴도치가 움직인다.
            else if(vec[x][y] == 'S')
            {
                if (vec[nx][ny] == '*') continue;
 
                vec[nx][ny] = 'S';
                visited[nx][ny] = visited[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
 
    // 정답이 나올 수 없는 경우.
    return -1;
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    vec.resize(n, vector<char>());
 
    string temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        for (int j = 0; j < m; j++)
        {
            vec[i].push_back(temp[j]);
 
            // 고슴도치와 물의 위치를 저장해놓는다.
            if (temp[j] == '*') q.push(make_pair(i, j));
            else if (temp[j] == 'S') start = make_pair(i, j);
        }
    }
 
    int result = bfs();
 
    if (result == -1) cout << "KAKTUS";
    else cout << result;
 
    return 0;
}
 

---

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

3055번: 탈출