[백준 22166] 창영이와 퇴근 - Java 문제풀이

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

 

문제

창영이의 퇴근길은 출근길과 조금 다르다. 창영이는 건강을 위해 따릉이를 빌려 타고 퇴근하는 습관을 기르고 있다.

창영이의 퇴근길은 N×N 크기의 격자로 표현된다. 창영이는 A1,1에서 출발하여 AN,N까지 이동할 계획이다. 창영이는 상하좌우 인접한 격자로 한 번에 한 칸씩 이동할 수 있다. 각 격자 Ar,c에는 자연수가 적혀 있는데, 이는 해당 지역의 높이를 뜻한다. 인접한 격자 사이의 높이 차이의 절댓값을 경사라고 하고, 경사가 클수록 경사가 가파르다고 하자.

따릉이는 가격에 따라 성능이 다르다. 비싼 따릉이는 경사가 가파르더라도 내리지 않고 타고 갈 수 있지만, 값싼 따릉이는 경사가 가파르면 힘들고 위험하기 때문에 내려서 이동해야 한다.

창영이는 최소한의 비용으로 따릉이를 빌려서, 따릉이에서 한 번도 내리지 않고 집에 도착하고 싶다. 그러기 위해선 창영이가 지날 수 있는 최대 경사의 최솟값을 알아야만 한다. 여러분들이 창영이를 도와주자.

 

입력

첫째 줄에 격자의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 격자의 높이 정보가 주어진다. 첫 번째로 주어지는 값이 A1,1이고, 마지막으로 주어지는 값이 AN,N이다.

 

출력

A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다.

풀이

접근법

1. 전형적인 최소신장트리의 문제이다
2. 프림 알고리즘을 이용하여 노드를 추가해가면서, 정점을 이으면 된다
3. 이 때, 간선의 길이를 높이 차이의 절댓값으로 두어 이 값이 최소인 지점 순서대로 연결해주면 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        int[][] arr = new int[N][N];
        StringTokenizer st;
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) arr[i][j] = Integer.parseInt(st.nextToken());
        }
        // 1. 전형적인 최소신장트리의 문제이다
        // 2. 프림 알고리즘을 이용하여 노드를 추가해가면서, 정점을 이으면 된다
        // [x좌표, y좌표, 경사도 순]
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        pq.add(new int[]{0, 0, 0});
        int ans = 0;
        int[] dx = new int[]{-1, 1 ,0, 0};
        int[] dy = new int[]{0, 0, -1, 1};
        boolean[][] visited = new boolean[N][N];
        while(!pq.isEmpty()) {
            int[] now = pq.poll();
            if (visited[now[0]][now[1]]) continue; // 이미 연결되 지점
            visited[now[0]][now[1]] = true;
            // 작은 순서대로 이어주니까, [N-1][N-1] 지점이 나올 때까지의
            // 최댓값을 구해주면 된다.
            ans = Math.max(ans, now[2]); 
            if(now[0] == N-1 && now[1] == N-1) break;
            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 >= N || visited[nx][ny]) continue;
                // 3. 이 때, 간선의 길이를 높이 차이의 절댓값으로 두어 이 값이 최소인 지점 순서대로 연결해주면 된다.
                pq.add(new int[]{nx, ny, Math.abs(arr[now[0]][now[1]] - arr[nx][ny])});
            }
        }

        System.out.println(ans);
    }
}

 

문제 읽는것부터 해서 6분 걸렸다 ! 전형적인 프림 알고리즘 문제이다.