백준 18128 (치삼이의 징검다리 건너기) - java

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

 

문제

치삼이는 가로로 N, 세로로 N만큼의 정사각형 모양 계곡을 지나가려고 한다. 하지만 엄청난 더위로 인해 물이 모두 말라버렸다!

계곡은 땅과 돌로 이루어져 있다. 전체 땅은 1×1크기의 땅들로 이루어져있고 땅에 돌이 존재할 수 있다. 그런데 계곡의 땅과 돌이 너무 뜨거워서 지나갈 수가 없다. 하지만 돌이 있는 부분은 물이 차오르면 식어서 지나갈 수 있게 된다. 다행히 마음씨 좋은 학생들이 치삼이를 위해 땅을 파서 물이 생성되는 곳을 만들어냈고 치삼이는 돌을 밟고 계곡을 지나가기로 했다. 물 생성지에는 땅이나 돌 모두 존재할 수 있다. 물은 물이 존재하는 위치에서 하루에 한 번 물과 인접한 곳으로 퍼진다. 이때, 대각선은 인접해 있다고 보지 않는다.

치삼이는 현재 시작지점(1, 1)에서 도착지점(N, N)까지 가려고 한다. 시작지점(1, 1)과 도착지점(N, N)의 위치에는 항상 돌이 존재하며 물과 만나지 않아도 치삼이가 이동할 수 있다. 치삼이가 이동하는 것에는 시간이 걸리지 않는다. 치삼이는 상, 하, 좌, 우, 대각선으로 이동할 수 있다. 이때 치삼이가 도착지점(N, N)의 위치까지 가장 빠르게 도착하는 경우 며칠이 걸리는지 알아보자.

 

유형 : BFS

 

접근 방식

• 치삼이의 이동에는 시간이 소요되지 않는다. 즉 물이 차올라 돌이 이동 가능한지를 판단하는 것이 중요하다.
• 위 문제를 해결하기 위해 가장 중요한 것은 1번의 BFS 수행을 통해 각 자리에 물이 몇시에 차오르는지 기록해 놓는 것이다.
  • 여기서 주의할 점은 시작점과 도착지의 시간을 0으로 설정하는 것이다.
• 그 다음에 치삼이를 BFS를 통해 이동시킨다.
  • 여기서 중요한 점은 치삼이의 이동에는 시간이 소요되지 않으므로 돌이 물에 차오르는 시간의 MAX값을 시간 값으로 비교해야 한다.
  • 즉 현재지점에 올 때까지 밟은 돌의 시간 중 가장 큰값을 기록하는 것이다. (해당 값이 작을수록 더 빠른 시간에 해당 지점까지 도착한 것이다.)
  • PQ를 사용해 시간 순으로 작은 값부터 탐색해 도착지에서의 시간을 비교한다.

 

전체 코드

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

public class Main {

    static int[] wx = {0,0,-1,1};
    static int[] wy = {1,-1,0,0};
    static int n,m;
    static int[][] board;

    static int[][] wv;

    static Queue<int[]> water = new ArrayDeque<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][n+1];
        wv = new int[n+1][n+1];

        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++){
                wv[i][j] = -1;
            }
        }

        for(int i = 1 ; i <= m ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            wv[x][y] = 0;
            water.add(new int[]{x,y});
        }

        for(int i = 1 ; i <= n ; i++){
            char[] arr = br.readLine().toCharArray();

            for(int j = 1 ; j <= n ; j++){
                board[i][j] = arr[j-1] - '0';
            }
        }

        waterGo();
        wv[n][n] = 0;
        int result = bfs();

        System.out.println(result);
        br.close();
    }

    static int[] dx = {0,0,-1,1,1,1,-1,-1};
    static int[] dy = {1,-1,0,0,1,-1,1,-1};

    static int bfs(){
        int[][] v = new int[n+1][n+1];
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++){
                v[i][j] = -1;
            }
        }

        PriorityQueue<int[]> q = new PriorityQueue<>(
                (x,y) -> x[2] - y[2]
        );

        v[1][1] = 0;
        q.add(new int[]{1,1,0});
        int result = - 1;

        while(!q.isEmpty()){
            int[] cur = q.poll();
            if(cur[0] == n && cur[1] == n){
                result = cur[2];
                break;
            }

            int curDay = cur[2];

            for(int i = 0 ; i < 8 ; i++){
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if(isOut(nx,ny) || board[nx][ny] == 0)
                    continue;

                int nextDay = Math.max(cur[2],wv[nx][ny]);

                if(v[nx][ny] == -1 || v[nx][ny] > nextDay){
                    v[nx][ny] = nextDay;
                    q.add(new int[]{nx,ny,v[nx][ny]});
                }
            }
        }


        return result;
    }

    static void print(int[][] arr){
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static void waterGo(){
        while(!water.isEmpty()){
            int[] cur = water.poll();

            for(int i = 0 ; i < 4 ; i++){
                int nx = cur[0] + wx[i];
                int ny = cur[1] + wy[i];

                if(isOut(nx,ny) || wv[nx][ny] != -1)
                    continue;

                wv[nx][ny] = wv[cur[0]][cur[1]] + 1;
                water.add(new int[]{nx,ny});
            }
        }
    }

    static boolean isOut(int x,int y){
        if(x < 1 || x > n || y < 1 || y > n)
            return true;

        return false;
    }
}