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

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

를 찾는 문제

5 4
9 1
2 7

접근

비용이 있는 맵에서 최단 경로를 찾음 + 음의 가중치 없음 -> 다익스트라 쓰자!

각 칸을 노드로 생각하고, 이동 자체를 간선으로 생각하고 풀었음.

핵심

int[][] grid : 지도 정보
int[][] dist : 최소 비용 저장 배열
PriorityQueue : 비용이 가장 적은 곳 부터 탐색하기 위함
Node : 큐에 담길 노드를 묶어주기 위함

코드

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

public class Main {
  static int N;
  static int[][] grid;
  static int[][] dist;
  static int[] dr = {-1, 1, 0, 0};
  static int[] dc = {0,0, -1, 1};

  static int tc = 1;

  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    while (true) {
      N = Integer.parseInt(br.readLine());

      if (N == 0) {
        break;
      }

      grid = new int[N][N];
      dist = new int[N][N];

      input(br);
      dijkstra();

      sb.append("Problem ").append(tc++).append(": ").append(dist[N-1][N-1]).append("\n");
    }
    br.close();
    System.out.println(sb);
  }

  static void input(BufferedReader br) throws  IOException {
    for (int r = 0; r < N; r++) {
      StringTokenizer st = new StringTokenizer(br.readLine(), " ");
      for (int c = 0; c < N; c++) {
        grid[r][c] = Integer.parseInt(st.nextToken());
        dist[r][c] = Integer.MAX_VALUE;
      }
    }
  }

  static void dijkstra() throws IOException {
    PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> o1.cost - o2.cost );

    dist[0][0] = grid[0][0];
    pq.add(new Node(0, 0, grid[0][0]));

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

      int currR = current.r;
      int currC = current.c;
      int currCost = current.cost;

      if (currCost > dist[currR][currC]) {
        continue;
      }
      for (int i = 0; i < 4; i++) {
        int nextR = currR + dr[i];
        int nextC = currC + dc[i];

        if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
          continue;
        }

        int nextCost = currCost + grid[nextR][nextC];

        if (nextCost < dist[nextR][nextC]) {
          dist[nextR][nextC] = nextCost;
          pq.add(new Node(nextR, nextC, nextCost));
        }
      }
    }
  }

  static class Node {
    int r ;
    int c;
    int cost;

    public Node(int r, int c, int cost) {
      this.r = r;
      this.c = c;
      this.cost = cost;
    }
  }
}

결론

음.

그냥 다익스트라 슉샤샷 하니까 풀린 문제.

다익스트라를 간만에 구현하려니까 힘들었는데… 심지어 자바라서 겁먹었는데 우선순위 큐를 그냥 날먹 불러올 수 있어서 편했다.