SWEA_D4_1249

📁 [D4_1249] 보급로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {
	static int N;
	static int[][] map;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int minCost;
	static int INF = Integer.MAX_VALUE;

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

		// 테스트케이스
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			sb.append("#").append(tc).append(" ");

			// 지도의 크기
			N = Integer.parseInt(br.readLine());

			// 값 저장 배열
			map = new int[N][N];

			// 입력
			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				String[] sstr = str.split("");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(sstr[j]);
				}
			}

			sb.append(dijkstra(0,0)).append("\n");
		}
		System.out.println(sb);
	}

    // 다익스트라 알고리즘
	static int dijkstra(int startR, int startC) {
        // 방문처리 배열
		boolean[][] visited = new boolean[N][N];
		// 출발지에서 자신까지의 최소복구시간
		int[][] minTime = new int[N][N];

        // 모든 배열값을 max 값으로 설정 ( 초기화 )
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				minTime[i][j] = INF;
			}
		}

		// int[] = 정점정보, 출발지에서 자신까지의 비용 r,c,cost
		PriorityQueue<int[]> pQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {

			// cost 비교
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
		});

		minTime[startR][startC] = 0;
		pQueue.offer(new int[] { startR, startC, minTime[startR][startC] });

        // BFS
		int r, c, minCost, nr, nc, current[];
		while (true) {
            // 도착지라면 끝내기
			if (r == N - 1 && c == N - 1)
				return minCost;


			// pQueue 안의 정점 중 출발지에서 자신으로의 비용이 최소인 정점의 정보
			current = pQueue.poll();
			r = current[0];
			c = current[1];
			minCost = current[2];

            // 방문한 곳이라면 통과
			if (visited[r][c])
				continue;

            // 방문처리
			visited[r][c] = true;
	
			// 현 정점의 인접정점 들여다보며 최소비용 갱신
			for (int i = 0; i < 4; i++) {
				nr = r + dr[i];
				nc = c + dc[i];
				if (nr >= 0 && nr < N && nc >= 0 && nc < N && minTime[nr][nc] > minCost + map[nr][nc]) {
					minTime[nr][nc] = minCost + map[nr][nc];
					pQueue.offer(new int[] { nr, nc, minTime[nr][nc] });
				}
			}
		}
	}
}

🤔 나의 생각

이 문제도 가중치가 있는 그래프 문제이다.
보통 가중치가 없는 최소비용은 도착지에 오면 끝이기 때문에 BFS로 해결하고 가중치가 있는 최소비용은 BFS로 구현한다면 방문체크나 최소값을 갱신해주어야 한다.
이 문제는 단일 출발지에서 다른 도착지로 양의 가중치를 가진 최소비용을 구하는 것이기 때문에 다익스트라 알고리즘을 사용하면 적절하다 !!
간선은 4방향으로 갈 수 있고 가중치는 깊이이다.
먼저 최소복구시간을 저장하는 배열을 생성한 뒤 max 값으로 초기화 시킨다.
그리고 시작점 부터 0을 집어넣고 다음 값들의 최소비용을 갱신하면서 끝점에 도달할 때까지 진행한다.
그러면 우선순위 큐에 의해 큐 내부에 정렬이 되어서 최소비용이 나오게 된다.