[SWEA JAVA] 1249. [S/W 문제해결 응용] 4일차 - 보급로

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution {
	public static int T, N, ans = 0;
	public static int[][] map, visited, MIN;
	public static int dr[] = { -1, 0, 1, 0 };
	public static int dc[] = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];

			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = str.charAt(j) - '0';
				}
			}

			ans = 0;
			getMinTime(0, 0, N - 1, N - 1);
			System.out.println("#" + tc + " " + ans);
		}
	}

	public static void getMinTime(int sr, int sc, int er, int ec) {
		final int INF = Integer.MAX_VALUE;
		visited = new int[N][N];
		MIN = new int[N][N];
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[2], o2[2]));

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				MIN[i][j] = INF;
			}
		}

		MIN[sr][sc] = 0;
		pq.offer(new int[] { sr, sc, MIN[sr][sc] });
		
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			int r= cur[0];
			int c = cur[1];
			int time = cur[2];
			
			if(visited[r][c] == 1) continue;
			visited[r][c] = 1;
			if(r==er && c==ec) {
				ans = time;
				return;
			}
			
			for(int d = 0;d<4;d++) {
				int nr = r + dr[d];
				int nc = c + dc[d];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
				if(visited[nr][nc] == 0 && MIN[nr][nc] > time + map[nr][nc]) {
					MIN[nr][nc] = time + map[nr][nc];
					pq.offer(new int[] { nr, nc, MIN[nr][nc] });
				}
				
			}
			
		}
		ans = -1;
		return;
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

 

다익스트라, 우선순위 큐 사용

 

## 풀이 사항
풀이 일자: 2024.09.22
풀이 시간: 60분
채점 결과: 정답
예상 문제 유형: 다익스트라

## 풀이 방법
1. 이차원 배열을 map, visited, min 세가지를 만들어 주고 오름차순 pq를 만들어준다.
2. min에는 각 맵의 시작점 부터 해당 지점까지 가는 최소 거리를 저장해주고 bfs를 통해 방문하지 않은 노드에 대해서 우선순위 큐에 삽입해준다.
3. 도착점에 도착했다면 해당 지점의 거리를 출력한다.