[백준] 26009번 : 험난한 등굣길 Gold2(G2) - JAVA[자바]

[Gold II] 험난한 등굣길 - 26009

문제 링크

성능 요약

메모리: 300912 KB, 시간: 772 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 6월 2일 12:26:37

문제 설명

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

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

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

입력

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

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

다음 K개 줄에 걸쳐 각 정체 구역의 정보 R,C,D가 주어진다. (1≤R≤N,1≤C≤M,0≤D≤3 000)

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

출력

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

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

 

접근 방법

1. 시간 절약을 위해서 교통 정체가 일어나는 사각형부근에 테두리를 색칠한다.
2. 색칠한 테두리를 제외하고 목적지까지 갈 수 있는지 확인한다.

풀이 코드

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

/**
 * 문제: Main_26009_험난한 등굣길 G2
 * 메모리: 300912KB
 * 시간: 772ms
 * 접근 방법:
 * 1. 시간 절약을 위해서 교통 정체가 일어나는 사각형부근에 테두리를 색칠한다.
 * 2. 색칠한 테두리를 제외하고 목적지까지 갈 수 있는지 확인한다.
 */
public class Main {
    static int N, M;
    static boolean[][] trafficBoard;
    static int[] dirX = {-1, 0, 1, 0};
    static int[] dirY = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        trafficBoard = new boolean[N][M];

        // Input
        int K = Integer.parseInt(br.readLine());
        for (int i = 1; i <= K; i++) {
            st = new StringTokenizer(br.readLine());
            int R = Integer.parseInt(st.nextToken()) - 1;
            int C = Integer.parseInt(st.nextToken()) - 1;
            int D = Integer.parseInt(st.nextToken());
            trafficBoard[R][C] = true; // D가 0일 수 있으므로 R,C에도 방문 처리
            trafficCheck(R, C, D);
        } // Input End

        go();
    }

    // 테두리를 방문 처리
    private static void trafficCheck(int r, int c, int d) {
        for (int i = 0; i < d; i++) {
            if (isIn(r - d + i, c + i)) trafficBoard[r - d + i][c + i] = true;
            if (isIn(r + i, c + d - i)) trafficBoard[r + i][c + d - i] = true;
            if (isIn(r + d - i, c - i)) trafficBoard[r + d - i][c - i] = true;
            if (isIn(r - i, c - d + i)) trafficBoard[r - i][c - d + i] = true;
        }
    }

    private static void go() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        int count = 0;
        trafficBoard[0][0] = true;
        while (!q.isEmpty()) {
            int size = q.size();
            for(int s = 0; s < size; s++) {
                int[] cur = q.poll();

                for (int i = 0; i < 4; i++) {
                    int nX = cur[0] + dirX[i];
                    int nY = cur[1] + dirY[i];
                    if(!isIn(nX,nY) || trafficBoard[nX][nY]) {
                        continue;
                    }

                    if (nX == N - 1 && nY == M - 1) {
                        System.out.println("YES");
                        System.out.println(count + 1);
                        return;
                    }

                    trafficBoard[nX][nY] = true;
                    q.add(new int[]{nX, nY});
                }
            }
            count++;
        }

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

    private static boolean isIn(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}

 

- 테두리만 색칠하는 센스를 기를 수 있는 좋은 문제이다.