[백준 / java] 3055 : 탈출

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

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

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

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

🔎 문제 정리

R행 C열의 지도 존재

• 고슴도치 (S)
  • 비버의 위치(D)까지 최소 이동 횟수로 이동해야함
  • 물과 돌 통과 불가
  • 물이 찰 예정인 칸으로도 이동 불가
  • 상하좌우로 이동
• 물 (*)
  • 돌 통과 불가
  • 비버의 위치로 확장 불가
  • 상하좌우로 확장
• 빈곳 (.)
• 돌 (x)

🔎 문제 해결 순서

1. 고슴도치의 위치, 현재 맵 등 입력 정보를 받아준다

2. bfs() & flood()

3. 먼저 bfs()에서 flood() 호출

   물이 차오를 예정인 곳에 고슴도치가 방문 불가능 하므로 먼저 물이 차오를 곳을 검토해준다.
   check 배열에 못가는 곳은 -1로 체크

   • 동서남북으로 물 흐르도록
   • 이미 방문했거나 돌이 있는 곳으로는 X
   • 종료 노드로는 물이 흐를 수 X

4. 다시 bfs()로

   이때 BFS란?
   Breadth-First Search
   그래프에서 탐색을 할때 깊게 탐색하는 것이 아니라 넓게 탐색하는 방법이다.
   반대로 DFS는 깊게 그래프를 탐색하는 방식이다.

   BFS이므로 Queue를 사용한다.
   반복문을 돌면서 check 배열에 이동횟수를 넣어준다.

   • 돌 or 물 있는곳 X
   • 이미 갔던곳 X
   • → 즉 0인 곳만 갈 수 있음

5. 종료노드에 도달못하면 false, 도달하면 true를 메인으로 넘겨준다

   • false : KAKTUS 출력
   • true : 이동 횟수를 출력

🔎 코드

package boj3055;

import java.io.*;
import java.util.*;

public class Main {
    static char[][] map;
    static int[][] check;
    static int[] DX = {1,-1,0,0};
    static int[] DY = {0,0,1,-1};
    static Queue<Node> water;
    static Node endNode;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        check = new int[R][C];

        Node startNode = new Node(0,0); // 고슴도치 위치
        water = new LinkedList<>();

        // map 입력받기
        for(int i = 0; i < R; i++){
            String line = br.readLine();
            for(int j = 0; j < C; j++){
                map[i][j] = line.charAt(j);
                if (line.charAt(j)== 'S'){  // 시작
                    startNode = new Node(i,j);
                }else if(line.charAt(j) == '*'){    // 물
                    check[i][j] = -1;
                    water.offer(new Node(i,j));
                }else if(line.charAt(j) == 'X'){    // 돌
                    check[i][j] = -1;
                }else if(line.charAt(j) == 'D'){    // 종료
                    endNode = new Node(i,j);
                }
            }
        }

        boolean flag = bfs(R,C,startNode);
        if(!flag)   System.out.println("KAKTUS");
        else System.out.println(check[endNode.x][endNode.y]);
    }

     static boolean bfs(int r, int c, Node startNode){
        Queue<Node> queue = new LinkedList<>();
        queue.offer(startNode);

        int time = 0;

        while(!queue.isEmpty()) {
            time++;
            flood(r,c);    // 물 흐름

            int size = queue.size();
            while(size-->0) {    // 현재 큐에 있는 횟수만큼 반복
                Node node = queue.poll();
                int minTime = check[node.x][node.y];

                for (int i = 0; i < 4; i++) {
                    int dx = node.x + DX[i];
                    int dy = node.y + DY[i];

                    if (dx < 0 || dx >= r || dy < 0 || dy >= c) { // 범위
                        continue;
                    } else if (check[dx][dy] == 0) {
                        check[dx][dy] = time;
                        queue.offer(new Node(dx, dy));
                    }

                    if (dx == endNode.x && dy == endNode.y) // 종료노드 도달시 끝
                        return true;


                }
            }


        }
        return false;   // 종료노드에 도달 불가
    }

    static void flood(int r, int c) {
        int size = water.size();

        for (int i = 0; i < size; i++) {
            Node node = water.poll();

            for (int j = 0; j < 4; j++) {
                int dx = node.x + DX[j];
                int dy = node.y + DY[j];

                if (dx < 0 || dx >= r || dy < 0 || dy >= c) { // 범위 초과
                    continue;
                } else if (check[dx][dy] == -1) {   // 이미 방문 or 돌
                    continue;
                } else if (dx == endNode.x && dy == endNode.y) {
                    continue;
                } else {
                    check[dx][dy] = -1;
                    water.offer(new Node(dx, dy));
                }
            }
        }
    }
}
    class Node{
        int x, y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }