[백준] 3055 - 탈출

3055번: 탈출

• 문제
  

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

• 입력
  

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

• ex)

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

• 출력
  

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

• ex)

  6

• 코드

  package day1;
  
  import java.io.BufferedReader;
  import java.io.FileInputStream;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.Queue;
  import java.util.StringTokenizer;
  
  public class ex_3055 {
      static char [][] land;
      static int [][] time;
      static int[]dx={1,-1,0,0};
      static int[]dy={0,0,1,-1};
      static Node dest;
      static int R,C;
      private static class Node{
          int x;
          int y;
          boolean water;
          public Node(int x,int y,boolean water){
              this.x=x;
              this.y=y;
              this.water=water;
          }
      }
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
          R=Integer.parseInt(st.nextToken());
          C=Integer.parseInt(st.nextToken());
          land=new char[R][C];
          time=new int[R][C];
          Queue<Node> q=new LinkedList<>();
          int[]src=new int[2];
          for(int i=0;i<R;i++){
              st = new StringTokenizer(br.readLine());
              String in=st.nextToken();
              for(int j=0;j<C;j++){
                  char input=in.charAt(j);
                  if(input=='D') dest=new Node(i,j,false);
                  else if(input=='S'){
                      time[i][j]=0;
                      src[0]=i;
                      src[1]=j;
                  }
                  else if(input=='*')q.add(new Node(i,j,true));
                  land[i][j]=input;
              }
          }q.add(new Node(src[0],src[1],false));
          boolean flag=false;
          while(!q.isEmpty()){
              Node now = q.poll(); //1. 큐에서 꺼내옴
              if(now.water){
                  for(int i=0;i<4;i++){//3.연결된 곳 순회
                      int cx=now.x+dx[i];
                      int cy=now.y+dy[i];
                      if(check_water(cx,cy)){//4.갈 수 있는가
                          land[cx][cy]='*';//5.체크인
                          Node next=new Node(cx,cy,true);
                          if(!q.contains(next)) q.add(next);//6.큐에 넣음
                      }
                  }
              }else{
                  for(int i=0;i<4;i++){//3.연결된 곳 순회
                      int cx=now.x+dx[i];
                      int cy=now.y+dy[i];
                      if(check_hedge(cx,cy)){//4.갈 수 있는가
                          time[cx][cy]=time[now.x][now.y]+1;//5.체크인
                          if(cx==dest.x && cy==dest.y){//2. 목적지인가
                              System.out.println(time[cx][cy]);
                              flag=true;
                              q.clear();
                              break;
                          }
                          Node next=new Node(cx,cy,false);
                          if(!q.contains(next)) q.add(next);//6.큐에 넣음
                      }
                  }
              }
          }
          if(!flag) System.out.println("KAKTUS");
      }static boolean check_hedge(int x,int y){
          if(x<R && x>=0 && y>=0 && y<C && time[x][y]==0) {
              if(land[x][y]=='D' || land[x][y]=='.') return true;
          }
          return false;
      }static boolean check_water(int x,int y){
          if(x<R && x>=0 && y>=0 && y<C && land[x][y]=='.' && time[x][y]==0) return true;
          return false;
      }
  }

• 아이디어
  • 고슴도치와 물을 하나의 큐로
  • visited를 DP로 하여 time에 저장
  • 물먼저 고슴도치 나중
  • 고슴도치와 물의 check 조건을 따로
  • 물이 여러개일 수 있음