[백준] 4485번 녹색 옷 입은 애가 젤다지?

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

4485번: 녹색 옷 입은 애가 젤다지?

핵심

(0,0)에서 시작하여 (n-1, n-1)로 갈 때 가장 최소의 코인을 잃은 상태로 가야 한다.

즉 다익스트라를 사용해야 한다.

 

 

정답 코드

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static List<Node>[] nodes;
    static int[] distance;
    static boolean[] check;
    static int[] dy = {0, 1, -1, 0};
    static int[] dx = {1, 0, 0, -1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = 1;
        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            nodes = new ArrayList[n * n];
            distance = new int[n * n];
            check = new boolean[n * n];
            for (int i = 0; i < n * n; i++) {
                nodes[i] = new ArrayList<>();
                distance[i] = Integer.MAX_VALUE;
            }
            int[][] map = new int[n][n];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    map[i][j] = sc.nextInt();
                }
            }

            int num = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < 4; k++) {
                        int y = i + dy[k];
                        int x = j + dx[k];
                        if (0 <= y && y < n && 0 <= x && x < n) {
                            nodes[num].add(new Node(x % n + y * n, map[y][x]));
                        }
                    }
                    num++;
                }
            }
            dij(0);
            sb.append("Problem " + testCase + ": " + (distance[n * n - 1] + map[0][0]) + "\n");
            testCase++;
        }
        System.out.println(sb);
    }

    private static void dij(int start) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        distance[start] = 0;
        q.offer(new Node(start, 0));

        while (!q.isEmpty()) {
            Node cur = q.poll();
            check[cur.num] = true;
            for (Node next : nodes[cur.num]) {
                if (!check[next.num]) {
                    if (distance[cur.num] + next.link < distance[next.num]) {
                        distance[next.num] = distance[cur.num] + next.link;
                        q.offer(new Node(next.num, distance[next.num]));
                    }
                }
            }
        }
    }
}

class Node implements Comparable<Node> {
    int num;
    int link;

    @Override
    public int compareTo(Node node) {
        return this.link - node.link;
    }

    public Node(int num, int link) {
        this.num = num;
        this.link = link;
    }
}

해설

우선 다익스트라를 사용하기 위해 나는 각 좌표를 노드로 생각하였다.

우선 첫 번째 테스트 케이스를 예시로 보면

5 5 4

3 9 1

3 2 7 

로 된 배열이다.

이것을 각각 0~8번 노드로 생각하고 아래와 같은 가중치를 두었다.

즉 0번 노드는 1,3번과 연결되어 있다. 나머지 노드도 각각 상하좌우로 연결되어 있다.

이를 이용하여 다익스트라를 사용하여 풀었다.

중요한 점이라고 생각되는 것은 각각의 노드의 번호를 구하는 것인데,

이는 x% n + y *n의 값이 각각의 노드 번호가 된다.

 

 

배운 점

좌표를 각각의 노드로 두고 상하좌우에 가중치를 두고 다익스트라를 사용하였다.

다른 사람들의 풀이를 보면 대부분 x와 y로 나누어 초기 세팅 없이 풀었다.

이러한 방식이 더 효율적일 것이라 생각하였다.

문제를 단순하게 풀었다고 끝나는 것이 아닌 다른 사람의 풀이를 보고 배울 점이 있다면 

그것을 보고 내 것으로 만들자.