백준 14461 (소가 길을 건너간 이유 7) - java

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

 

문제

 

소가 길을 건너는 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에는 작은 정사각형 목초지가 N×N (3 ≤ N ≤ 100) 격자로 이루어져 있다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. 이 농장에 사는 소 베시는 한 목초지에서 상하좌우로 인접한 다른 목초지로 이동할 수 있지만, 교통사고를 피하기 위해 차가 안 오는지 확인하고 길을 건너야 한다. 길을 건너는데는 T초 (0 ≤ T ≤ 1,000,000)가 걸린다.

존이 베시에게 체스 대결을 신청했다. 베시는 북서쪽 끝에 있는 목초지에서 남동쪽 끝에 있는 존의 집으로 가야 한다. 길이 멀기 때문에 베시는 가는 도중에 배가 고파진다. 그래서 길을 세 번 건널 때마다 목초지에 있는 풀을 먹어야 한다. 존의 집에 도착할 때도 해당되지만, 출발할 때는 해당되지 않는다. 목초지마다 풀이 자란 정도가 달라서, 풀을 먹는데 걸리는 시간도 다르다.

베시가 가능한 한 빨리 존의 집에 도착할 수 있도록 도와주자.

 

유형 : 다익스트라

 

접근 방식

• 3번마다 목초지의 풀을 먹는 조건이 있기 때문에 3차원 dp 배열을 응용한 다익스트라를 사용한다.

 

코드

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

public class BOJ_14461_소가_길을_건너간_이유_7 {

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

    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());
        t = Integer.parseInt(st.nextToken());

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

        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            for(int j = 1 ; j <= n ; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        long[][][] dp = new long[n+1][n+1][4];
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n ; j++) {
                for(int k = 0 ; k <= 3 ; k++) {
                    dp[i][j][k] = Long.MAX_VALUE;
                }
            }
        }

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> Long.compare(x.v,y.v)
        );

        dp[1][1][0] = 0;
        pq.add(new Node(1,1,0,0));

        while(!pq.isEmpty()) {
            Node cur = pq.poll();

            if(dp[cur.x][cur.y][cur.c] < cur.v)
                continue;

            for(int i = 0 ; i < 4 ; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                int nc = cur.c + 1;

                if(isOut(nx,ny))
                    continue;

                long nextV = cur.v + t + ((nc == 3) ? board[nx][ny] : 0);

                if(nc == 3)
                    nc = 0;

                if(dp[nx][ny][nc] > nextV) {
                    dp[nx][ny][nc] = nextV;
                    pq.add(new Node(nx,ny,nc,nextV));
                }
            }
        }

        Long min = Math.min(Math.min(dp[n][n][0],dp[n][n][1]),dp[n][n][2]);

        System.out.println(min);

        br.close();
    }

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

        return false;
    }

    static class Node {
        int x;
        int y;
        int c;
        long v;


        Node(int x,int y,int c,long v) {
            this.x = x;
            this.y = y;
            this.c = c;
            this.v = v;
        }
    }
}