[백준] 탈출

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

3055번: 탈출

BFS를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

고슴도치가 비버굴로 이동을 해야하는데, 물이 차있는 곳에서 물이 확산되어 홍수처럼 물이 불어납니다. 이 때, 고슴도치는 물이 차있거나, 돌을 지날 수 없을 때, 고슴도치가 비버굴로 이동할 수 있는 가장 빠른 시간을 출력해야 합니다. 

 

만약 이동이 불가능 한 경우 "KAKTUS"를 출력해야 합니다. 

 

<Solution>

BFS를 이용해야 하는 것이 확실한데, 물이 차올라서 해결하기 조금 까다롭습니다. 

 

고슴도치는 물이 찰 예정인 곳으로도 이동이 불가능하므로, 물이 먼저 확산하고 고슴도치가 이동하는 형태로 BFS를 하면 될 것을 예상할 수 있습니다. 

 

따라서 queue에 struct k를 넣게 되는데, 

struct k{
    int r, c; // 상태
    int time; // 답구하기 위해
    int type; // 0 이면 물 1 이면 고슴도치
};

다음과 같이 

상태를 위한 r,c

답을 구하기 위한 time

고슴도치인지, 물인지를 구분하기 위한 type

 

이렇게 structure를 구성하고, 

QUEUE = [초기 물의 위치 1, 초기 물의 위치 2, ... ,초기 고슴도치의 위치] 이렇게 queue를 구성하고 BFS를 이용하면 되는 것을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
#define MAXN (50)
int R, C;//지도 세로, 가로 크기
char map[MAXN+10][MAXN+10];
int when[MAXN+10][MAXN+10];
 
 
void InputData(){
    cin >> R >> C;
    for (int i=1; i<=R; i++){
        cin >> &map[i][1];
    }
}
 
struct k{
    int r, c; // 상태
    int time; // 답구하기 위해
    int type; // 0 이면 물 1 고슴도치
};
 
int d_row[] = {0, 0, 1, -1};
int d_col[] = {1, -1, 0, 0};
 
int solution(){
 
    k initial_ppl;
    // build when array by bfs
    queue <k> my_q;
    for(int i=1; i<=R; i++){
        for(int j =1; j<= C; j++){
            if(map[i][j] == '*'){
                my_q.push((k){i,j,0,0});
            }
            if(map[i][j] == 'S'){
                initial_ppl.r = i;
                initial_ppl.c = j;
                initial_ppl.time = 0;
                initial_ppl.type = 1;
            }
        }
    }
    // 물이 먼저 확산되어야 하므로 고슴도치를 나중에 넣는다.
    my_q.push(initial_ppl);
    // visited 표시
    map[initial_ppl.r][initial_ppl.c] = 'X';
     
 
    while(!my_q.empty()){
        k e = my_q.front(); my_q.pop();
 
        for(int i =0;i<4; i++){
            // check type
            int new_r, new_c;
            if(e.type == 0){ // 물이면 그냥 확산
                new_r = e.r + d_row[i];
                new_c = e.c + d_col[i];
 
                if(map[new_r][new_c] == '.'){
                    map[new_r][new_c] = '*';
                    my_q.push((k){new_r,new_c,e.time+1, 0});
                }
            }
            else{ // 고슴도치면
                new_r = e.r + d_row[i];
                new_c = e.c + d_col[i];
 
                if(map[new_r][new_c] == 'D') return e.time+1;
 
                if(map[new_r][new_c] == '.'){
                    map[new_r][new_c] = 'X';
                    my_q.push((k){new_r,new_c,e.time+1, 1});
                }
            }
        }
 
    }
    return -1;
 
 
 
}
 
int main(){
    int ans = -1;


    InputData();//입력 받는 부분
    // 여기서부터 작성 

    ans = solution();

    if (ans == -1) cout << "KAKTUS" << endl;//출력 하는 부분
    else cout << ans << endl;

    return 0;
}