[BOJ] 3055 탈출 - JAVA

1. 문제

3055번: 탈출

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

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

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

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

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

---

2. 풀이

정적 변수

int R,C	크기
char[][] map	지도
int[][] deltas	움직일 수 있는 방향

 

main

1.  덱을 만든다. 물은 앞, 고슴도치는 뒤에 넣어서 한 depth당 순서대로 물-고슴도치 순으로 탐색할 수 있도록 한다. 문제에서는 고슴도치가 먼저 이동하고 그 후 물이 지나간다고 했지만, 다음 시간에 물이 지나갈 자리에 고슴도치가 이동할 수 없으므로 문제를 풀 때는 물을 이동시킨 후 고슴도치를 이동시킨다.

2.  answer에 bfs결과를 저장한다. 만약 -1이라면 KAKTUS를, 아니라면 answer을 출력한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   R = Integer.parseInt(st.nextToken());
   C = Integer.parseInt(st.nextToken());
   map = new char[R][C];

   Deque<int[]> deque = new ArrayDeque<>();

   for (int r = 0, c = 0; r < R; r++, c = 0) {
      for (char ch : in.readLine().toCharArray()) {
         if (ch == 'S') {
            deque.offerLast(new int[]{r,c,'S'});
         } else if (ch == '*') {
            deque.offerFirst(new int[]{r,c,'*'});
         }
         map[r][c++] = ch;
      }
   }

   int answer = BFS(deque);
   if(answer < 0) System.out.println("KAKTUS");
   else System.out.println(answer);
}

 

범위 체크

범위에서 벗어나지 않았고, 돌이 아니라면 true를 리턴한다.

private static boolean isValid(int nr, int nc){
   return nr >= 0 && nr < R && nc >= 0 && nc < C && map[nr][nc] != 'X';
}

 

BFS

1.  deque이 빌 때까지 반복하되, 반복문 안에서 deque의 현재 사이즈만큼 또 반복해서 요소를 뽑는다. 이렇게 하면 depth별로 탐색을 할 수 있다.

2.  만약 비어있는 공간'.'이라면 map[nr][nc]에 현재요소의 종류(S 또는 *)를 char로 변경해서 저장한다. deque의 뒤에 추가한다. 물과 고슴도치를 구분하지 않는 이유는 depth별로 탐색하고 있기 때문이다. 물이 먼저 지나간 자리에는 고슴도치가 당연히 접근할 수 없고, 고슴도치가 먼저 지나간 자리는 이후에 물이 퍼져도 이미 지나갔기 때문에 신경쓰지 않아도 된다. 

3.  map[nr][nc]가 'D'고, 현재 요소가 'S'라면 고슴도치가 비버 집에 도달한 것이다. answer을 반환한다.

4.  3에서 반환되지 않는다면 -1을 반환한다.

private static int BFS(Deque<int[]> deque){
   int[] now;
   int nr, nc;
   int answer = 0;
   while(!deque.isEmpty()){
      answer++;
      for(int s=0, size=deque.size();s<size;s++){
         now = deque.poll();
         for (int[] d : deltas) {
            nr = now[0] + d[0];
            nc = now[1] + d[1];
            if(!isValid(nr,nc)) continue;
            if(map[nr][nc] == '.'){
               map[nr][nc] = (char)now[2];
               deque.offer(new int[]{nr,nc,now[2]});
            }else if(map[nr][nc]=='D' && now[2]=='S'){
               return answer;
            }
         }
      }
   }

   return -1;
}

 

---

3. 결과