[SWEA] 1249 보급로

AngJ·1일 전

SWEA 다익스트라 코딩테스트

코딩테스트

목록 보기

21/22

문제

SWEA_1249_보급로

요약

출발지에서 목적지까지 도착가능한 가장 최소의 시간을 구해라.
위치마다 지나가는데 기다려야하는 시간이 있다. (단, 0 ~ 9 사이의 값)
전체 맵의 크기는 N x N으로 0~100 사이의 값

접근

이 문제는 가중치가 음수가 아닌 양수인 그래프의 최소 비용 경로를 찾는 문제이다.
따라서, Djikstra를 사용해서 풀 수 있다. (벨만포드도 가능은 함)

다익스트라는 그리디한 BFS (출발지에서 최소 거리인 정점들을 선택해나가면서 최단 거리를 구하는 방식)

알고리즘

Djikstra

map[][] 초기환경 세팅
dist[][] 생성
dist[][]를 INF(Infinity) 값으로 채움
dist[0][0] = 0;

PriorityQueue 생성 (가중치를 오름차순 정렬) // PQ가 관리하는 값: 정점 위치 & 해당 위치까지의 최소거리
PQ에 첫번째 vertex 삽입

while(PQ is not empty)
	
    vertex : pq에서 꺼낸 정점
	if vertex.cost is not Minimum : vertex의 cost가 최소 비용 거리인지 확인
    	continue;
    
    for i 0 to 4 // 4방 돌리기
    	nr, nc
        not isinRange(nr, nc) continue // 범위 벗어나는지 확인
        
        cost = dist[vertex.x][vertex.y] + map[nr][nc]
        if (cost < dist[nr][nc]) // 기존의 다음 정점의 도착 최소 비용보다 적은지 체크
        	dist[nr][nc] = cost
            pq.offer(new int[]{nr, nc, map[nr][nc]})

dist[][] 2차원 배열에 각 정점별 도착 가능한 최소 비용을 저장

이때 dist는 모두 INF(무한대)값으로 초기화!

PriorityQueue를 사용해 최소거리가 되는 정점들로 이동

제출코드

import java.util.*;
import java.io.*;
 
public class Solution {
    static int[][] map;
    static int N;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int[][] dist;
    static final int INF = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws Exception {
		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++) {
		    N = Integer.parseInt(br.readLine());
		    map = new int[N][N];
		    
		    for (int i = 0; i < N; i++) {
		        char[] list = br.readLine().toCharArray();
		        for (int j = 0; j < N; j++) {
		            map[i][j] = list[j] - '0';
		        }
		    }// end of map 초기화
		    
		    // 가중치를 계산해서 가장 적은 것들만 선택해서 최종적으로 도달하기 위해 메모하는 큐
		    PriorityQueue<int[]> pq = new PriorityQueue<>(
	            (a, b) -> Integer.compare(a[2], b[2])
	        );
	        
	        // 위치별 최소 누적 비용 저장
	        dist = new int[N][N];
	        for (int r = 0; r < N; r++) {
                Arrays.fill(dist[r], INF);
            }
	        
	        dist[0][0] = 0; // 시작위치 초기화
	        
	        // 시작 값 집어넣음
	        pq.offer(new int[]{0, 0, 0});
	        
	        while(!pq.isEmpty()) {
	            int[] vertex = pq.poll();
	            int x = vertex[0];
	            int y = vertex[1];
	            int weight = vertex[2];
	            if (weight > dist[x][y]) continue; // 해당 위치의 값이 최소인지 먼저 확인
	            
	            for (int d = 0; d < 4; d++) {
	                int nr = x + dr[d];
	                int nc = y + dc[d];
	                
	                if (!isinRange(nr, nc)) continue; // 범위 내인지 확인
	                
	                // 누적 값 업데이트
	                if (dist[nr][nc] > dist[x][y] + map[nr][nc]) {
	                    dist[nr][nc] = dist[x][y] + map[nr][nc];
	                    pq.offer(new int[]{nr, nc, dist[nr][nc]});
	                }
	            }
	        }
		    sb.append("#").append(tc).append(" ").append(dist[N-1][N-1]).append("\n");
		} // end of tc
		System.out.print(sb.toString());
    }// end of main
    
    static boolean isinRange(int r, int c) {
        return (r >= 0 && r < N && c >= 0 && c < N);
    }
}