[백준 / Java] 4485번: 녹색 옷 입은 애가 젤다지? (골드4)

문제 풀이 날짜: 2023.10.05
포스트 작성일: 2023.10.05

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 4485번: 녹색 옷 입은 애가 젤다지? (골드4)

 

키워드

다익스트라 (BFS + DP)

 

풀이 접근법

• 그래프의 시작점에서 끝까지 최소 비용으로 이동해야 한다. → 다익스트라 사용
  • 단순히 BFS로만 DP값을 갱신시키면 원하는 답이 잘 나오지 않는다. 따라서 우선순위 큐를 사용하는 다익스트라를 이용할 필요가 있다.
• 주어진 인접 행렬은 상하좌우로 노드가 연결된 그래프로 볼 수 있다. 따라서 사방탐색을 하며 이동 가중치의 합을 갱신시킨다.
• 이 때, 가중치의 합을 저장하는 DP 배열의 값이 이전보다 더욱 작은 값으로 갱신되었다면 해당 정점을 경유하는 다른 경로 또한 더욱 짧은 길이로 갱신될 수 있다.
• 따라서 해당 정점의 방문 여부와 무관하게 DP값이 갱신되었다면 재탐색(Queue에 add())한다.
• 도착지점에 다다를 때까지 위 과정을 반복한다.

 

코드

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

public class Main {

	private static int N;

	private static int[][] matrix;
	private static int[][] DP;

	private static int[] dr = { 0, 1, -1, 0 };
	private static int[] dc = { 1, 0, 0, -1 };

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

		int tc = 1;
		StringBuilder sb = new StringBuilder();
		while ((N = Integer.parseInt(br.readLine())) != 0) {
			matrix = new int[N][N];
			DP = new int[N][N];

			StringTokenizer st;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					matrix[i][j] = Integer.parseInt(st.nextToken());
					DP[i][j] = Integer.MAX_VALUE;
				}
			}

			dijkstra(0, 0);
			
			sb.append("Problem ").append(tc++).append(": ")
			.append(DP[N - 1][N - 1]).append("\n");
		}

		System.out.print(sb);
	}

	private static void dijkstra(int startR, int startC) {
		PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.dist, o2.dist));

		DP[startR][startC] = matrix[startR][startC];
		pq.add(new Node(startR, startC, DP[startR][startC]));

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

			if (n.row == N - 1 && n.col == N - 1) {
				return;
			}

			int nr = 0;
			int nc = 0;
			for (int i = 0; i < dr.length; i++) {
				nr = n.row + dr[i];
				nc = n.col + dc[i];

				if (!isValid(nr, nc)) {
					continue;
				}

				//DP값이 갱신됐다면 재탐색 해야하므로 별도의 visit 처리는 하지 않는다.
				if (DP[n.row][n.col] + matrix[nr][nc] < DP[nr][nc]) {
					DP[nr][nc] = DP[n.row][n.col] + matrix[nr][nc];
					pq.add(new Node(nr, nc, DP[nr][nc]));
				}
			}
		}

		return;
	}

	private static boolean isValid(int nr, int nc) {
		return (nr > -1 && nc > -1 && nr < N && nc < N);
	}
}

class Node {
	int row;
	int col;
	int dist;

	public Node(int row, int col, int dist) {
		this.row = row;
		this.col = col;
		this.dist = dist;
	}
}

---

 

 

git 링크

(git 링크 첨부)