문제

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

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

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

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

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

입력

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

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

출력

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

예제

예제 입력
5 4
.D.*
....
..X.
S.\*.
....

예제 출력
4

접근

  • 역시 BFS문제이다.
  • 물이 차오를 예정인 곳에는 접근할 수 없음에 주의하자.

내가 생각한 풀이

  • BFS를 통해 시간이 지남에 따라 물이 갈 수 있는 곳, 고슴도치가 갈 수 있는 곳을 계산했다.
    • 이 때 물이 차오를 예정인 곳에는 고슴도치가 갈 수 없으므로 물이 먼저 차오르게 한 후 고슴도치를 이동시켰다.
  • 매 분마다 두 번의 BFS를 진행해야 하기 때문에 2개의 queue를 통해 BFS를 각각 진행시켰다.
    • 매 번 queue에 push되는 원소의 수를 count한 후 그 다음 분에 그만큼의 BFS만 수행되게 하였다.

코드

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int R,C,count=0,qcount=0,dqcount=1,dp[51][51] = {0, };
bool chk(int a, int b){return (a>=0 && b>=0 && a<R && b<C);}
struct xy{
  int y;
  int x;
};

int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

int main(void){
  string s[51];
  bool c[51][51] = {0, };
  queue<struct xy> q;
  queue<struct xy> dq;
  struct xy dochi, bibu;
  cin>>R>>C;
  for(int i = 0; i<R;i++) cin>>s[i];
  for(int i = 0; i<R;i++){
    for(int j = 0 ;j<C;j++){
      if(s[i][j] == '*'){q.push({i,j}); qcount++;}
      if(s[i][j] == 'S'){dochi.y = i; dochi.x = j;}
      if(s[i][j] == 'D'){bibu.y = i; bibu.x = j;}
    }
  }
  dq.push({dochi.y, dochi.x});
  s[dochi.y][dochi.x] = '0';
  while(!dq.empty()){ //고슴도치가 이동할 수 없을 때까지 진행
    int tqcount = 0, tdqcount = 0;
    for(int a = 0 ;a<qcount;a++){ //물이 차오를 예정인 곳은 갈 수 없으므로 물에 대한 BFS부터 진행
      struct xy t = q.front();
      q.pop();
      for(int i = 0 ;i<4;i++){
        int y = t.y + d[i][0], x = t.x + d[i][1];
        if(chk(y,x) && c[y][x] == 0 && (s[y][x] == '.')){
          q.push({y,x});
          c[y][x] = 1;
          s[y][x] = '*';
          tqcount++; //이번 회차에 queue에 추가된 갯수만큼 다음번에 그 주변으로 물이 퍼지게 함. while(!q.empty()) 조건을 써버리면 당연히 안됨..!
        }
      }
    }
    qcount = tqcount;
    for(int a = 0 ;a<dqcount;a++){
      struct xy dt = dq.front();
      dq.pop();
      for(int i = 0 ;i<4;i++){
        int y = dt.y + d[i][0], x = dt.x + d[i][1];
        if(chk(y,x) && c[y][x] == 0 && (s[y][x] == '.' || s[y][x] == 'D')){
          if(s[y][x] == 'D'){
            // s[y][x] = 'S';
            dp[y][x] = dp[dt.y][dt.x] + 1;
            cout<<dp[y][x];
            return 0;
          }
          dq.push({y,x});
          c[y][x] = 1;
          s[y][x] = 'S';
          dp[y][x] = dp[dt.y][dt.x] + 1;
          tdqcount++; //고슴도치가 갈 수 있는 경로 역시 마찬가지
        }
      }
    }
    dqcount = tdqcount;
  }
  if(s[bibu.y][bibu.x] == 'D') cout<<"KAKTUS"; //만약 BFS가 모두 진행되었는데도 고슴도치가 도달하지 못했다면 KAKTUS 출력
  else cout<<dp[bibu.y][bibu.x];
  return 0;
}