[백준 14461] 소가 길을 건너간 이유 - Java 문제풀이

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

 

문제

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

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

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

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

 

입력

첫 줄에 N과 T가 주어진다. 다음 N줄에는 목초지마다 풀을 먹는데 걸리는 시간이 N×N의 형태로 주어진다. 각각의 수는 모두 100,000 이하이다.

출력

베시가 존의 집까지 가는데 걸리는 최소 시간을 출력한다.

풀이

접근법

1. 각 노드별로 0번, 1번, 2번으로 접근했다고 했을 때의 경우가 다 다르니까 visited배열은 3차원으로 만들자
2. 가장 빨리 갈 수 있는 방법이니까 다익스트라로 최단거리로만 계산하자.

 

코드

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

public class Main {
    private static class Node implements Comparable<Node> {
        int x, y, time;
        long moved;
        Node(int x, int y, int time, long moved) {
            this.x = x;
            this.y = y;
            this.time = time;
            this.moved = moved;
        }

        @Override
        public int compareTo(Node o) {
            return this.moved < o.moved ? -1 : 1;
        }

        @Override
        public String toString() {
            return "[Node x="+x+", y="+y+", time="+time+", moved="+moved+"]";
        }
    }
    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 T=Integer.parseInt(st.nextToken());
        int[][] arr = new int[N][N];
        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. 각 노드별로 0번, 1번, 2번으로 접근했다고 했을 때의 경우가 다 다르니까 visited배열은 3차원으로 만들자
        boolean[][][] visited = new boolean[N][N][3];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, 0, 0, 0L));
        long ans = 0;
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};
        // 2. 가장 빨리 갈 수 있는 방법이니까 다익스트라로 최단거리로만 계산하자.
        while(!pq.isEmpty()) {
            Node now = pq.poll();
            if (visited[now.x][now.y][now.time]) continue;
            if (now.x == N-1 && now.y == N-1) {
                ans = now.moved;
                break;
            }
            visited[now.x][now.y][now.time] = true;
            int nt = now.time + 1;
            if (nt == 3) nt = 0;
            long nm = now.moved + T;
            for(int k=0;k<4;k++) {
                int nx = now.x + dx[k];
                int ny = now.y + dy[k];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny][nt]) continue;
                pq.add(new Node(nx, ny, nt, nt == 0 ? nm + arr[nx][ny] : nm));
            }
        }

        System.out.println(ans);

    }

}

 

생각보다 엄청 오래 걸렸다... 거의 2시간 ?

원래 알고리즘 분류 안보고 푸는데, 처음에는 DP+DFS로 접근했다가 계속 답이 안나왔다.(DFS + 백트래킹으로 했을 때에는 시초가 나왔다.)

그래서 분류를 보니까 다익스트라로 되어 있어서 그런 방향으로 접근하니 바로 풀렸다...

역시 다양하게 접근해야 하는 것 같다.