[백준 26009] 험난한 등굣길 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/26009

 

문제

통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 N x M 인 격자로 나타낼 수 있는데, i행 j열에 해당하는 칸을 (i, j) 로 나타낼 때 재헌이는 현재 (1, 1)에, 학교는 (N, M)에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다.

등굣길은 순탄치만은 않은데, 이 지역에는 K개의 정체 구역이 있다. 𝑖$i$번째 정체 구역은 세 정수 Ri, Ci, Di로 표현되며, 이는 (Ri, Ci)로부터 거리가 Di 이하인 칸들에는 극심한 교통 정체가 일어나고 있음을 의미한다. 두 칸 (R1, C1), (R2, C2) 사이의 거리는 |R1 - R2| + |C1 - C2|와 같다.

재헌이는 교통 정체가 일어나고 있는 칸을 방문하면 수업에 지각하게 되며, 방문하지 않는다면 지각하지 않고 무사히 수업을 들을 수 있다. K개의 정체 구역에 대한 정보가 주어졌을 때 재헌이가 지각하지 않고 1교시 수업을 들을 수 있을지 알아보자. 또한 재헌이는 최대한 일찍 학교에 도착하려 하기 때문에, 만약 재헌이가 지각하지 않고 수업을 들을 수 있다면 최소 몇 번의 이동으로 수업을 들으러 갈 수 있는지도 구해보자.

 

입력

첫째 줄에 격자의 크기 N, M 이 주어진다. (2 ≤ N, M ≤ 3000)

다음 줄에 정체 구역의 수 K가 주어진다. (1 ≤ K ≤ 3000)

다음 K개 줄에 걸쳐 각 정체 구역의 정보 Ri, Ci, Di 가 주어진다. (1 ≤ Ri ≤ N, 1 ≤ Ci  ≤ M, 0 ≤ Di ≤ 3000)

(1, 1) 또는 (N, M)에 교통 정체가 일어나고 있는 경우는 주어지지 않는다.

 

출력

재헌이가 지각하지 않고 수업을 들을 수 있으면 YES를 출력하고, 다음 줄에 최소 이동 횟수를 출력한다.

만약 지각하지 않고 수업을 들을 수 없다면 NO를 출력한다.

풀이

접근법

1. 갈 수 없는 모든 곳을 막는 것은 비효율적이다. 왜냐면 바운더리만 막아줘도 그 내부는 못들어가기 때문이다. 따라서 바운더리에만 못들어간다는 표시를 하자.
2. 최단경로를 구하는 거니까 BFS 사용하면 될 것 같다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());
        int K=Integer.parseInt(br.readLine());
        boolean[][] visited = new boolean[N][M];
        for(int i=0;i<K;i++) {
            st = new StringTokenizer(br.readLine());
            int x=Integer.parseInt(st.nextToken())-1;
            int y=Integer.parseInt(st.nextToken())-1;
            int d=Integer.parseInt(st.nextToken());
            set(visited, x, y, d, N, M);
        }
        Queue<int[]> queue = new LinkedList<>();
        visited[0][0] = true;
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};
        queue.add(new int[]{0, 0, 0});
        // 2. 최단경로를 구하는 거니까 BFS 사용하면 될 것 같다.
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            for(int k=0;k<4;k++) {
                int nx = now[0] + dx[k];
                int ny = now[1] + dy[k];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny]) continue;
                if (nx == N-1 && ny == M-1) {
                    System.out.println("YES");
                    System.out.println(now[2]+1);
                    return;
                }
                queue.add(new int[]{nx, ny, now[2] + 1});
                visited[nx][ny] = true;
            }
        }

        System.out.println("NO");
    }

    private static void set(boolean[][] visited, int x, int y, int d, int N, int M) {
        // 1. 갈 수 없는 모든 곳을 막는 것은 비효율적이다. 왜냐면 바운더리만 막아줘도 그 내부는 못들어가기 때문이다. 
        // 따라서 바운더리에만 못들어간다는 표시를 하자.
        for(int i=0;i<=d;i++) { // i 는 x의 d
            int minx = x - i;
            int maxx = x + i;
            int miny = y - (d-i);
            int maxy = y + (d-i);
            if (minx >= 0) {
                if (miny>=0) visited[minx][miny] = true;
                if (maxy<M) visited[minx][maxy] = true;
            }
            if (maxx < N) {
                if (miny>=0) visited[maxx][miny] = true;
                if (maxy<M) visited[maxx][maxy] = true;
            }

        }
    }
}

 

시초를 해결하기 위해서 바운더리 기준으로 못가게 막는다는 것을 알아차리는 데에 오랜 시간이 걸렸다.