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

문제 링크

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

풀이 과정

다익스트라 문제입니다.

for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++) {
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            int from = x * N + y;

            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                Edge to = new Edge(nx * N + ny, map[nx][ny]);
                adj[from].add(to);
            }
        }
    }
}

문제에서 그래프가 2차원 배열 형태로 주어지기 때문에, 먼저 2차원의 배열 인덱스를 1차원으로 변환하여 인접 리스트 형태로 adj에 저장합니다.

PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(0, map[0][0]));
dist[0] = map[0][0];

while (!pq.isEmpty()) {
    Edge now = pq.poll();

    for (Edge next : adj[now.vertex]) {
        if (dist[next.vertex] > dist[now.vertex] + next.cost) {
            dist[next.vertex] = dist[now.vertex] + next.cost;
            pq.add(next);
        }
    }
}

우선순위 큐에, 링크가 움직일 첫 번째 위치 (0, 0)에 대한 정보를 넣고 다익스트라 알고리즘을 실행합니다. 시작 위치 (0, 0)에 존재하는 검정색 루피는 무조건 획득하므로, dist[0]은 그 값으로 초기화합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N;
        int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
        int TC = 1;

        while ((N = Integer.parseInt(br.readLine())) != 0) {
            int[][] map = new int[N][N];

            for (int i = 0; i < N; i++)
                map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            ArrayList<Edge>[] adj = new ArrayList[N * N];
            int[] dist = new int[N * N];
            Arrays.fill(dist, Integer.MAX_VALUE);

            for (int i = 0; i < adj.length; i++) adj[i] = new ArrayList<>();

            for (int x = 0; x < N; x++) {
                for (int y = 0; y < N; y++) {
                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];
                        int from = x * N + y;

                        if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                            Edge to = new Edge(nx * N + ny, map[nx][ny]);
                            adj[from].add(to);
                        }
                    }
                }
            }

            PriorityQueue<Edge> pq = new PriorityQueue<>();
            pq.add(new Edge(0, map[0][0]));
            dist[0] = map[0][0];

            while (!pq.isEmpty()) {
                Edge now = pq.poll();

                for (Edge next : adj[now.vertex]) {
                    if (dist[next.vertex] > dist[now.vertex] + next.cost) {
                        dist[next.vertex] = dist[now.vertex] + next.cost;
                        pq.add(next);
                    }
                }
            }

            System.out.println("Problem " + TC++ + ": " + dist[N * N - 1]);
        }
    }

    static class Edge implements Comparable<Edge> {
        int vertex, cost;

        public Edge(int vertex, int cost) {
            this.vertex = vertex;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.cost, o.cost);
        }
    }
}