백준 | 20046번. Road Reconstruction - 다익스트라

⬛ 백준 20046번. Road Reconstruction - 다익스트라

https://www.acmicpc.net/problem/20046

20046번: Road Reconstruction

문제

홍수의 발생으로 인해 도시의 도로들이 유실되어 많은 ICP(International Computational Plan) 시민들이 불편을 겪고 있다. 도시는 아래와 같은 격자 형태로 표현이 된다고 가정하자. 검정색 단위 격자가 ‘단위도로’를 의미하며 흰색 단위 격자는 도로가 없었거나 유실된 상태를 의미한다. X로 표시된 단위 격자는 도로를 건설할 수 없는 곳을 의미한다.

도시의 차들은 단위 도로 상에서 가로나 세로 방향으로만 움직인다고 가정했을 때 도시의 기능을 회복시키기 위해 맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 도시의 차들이 가는 경로를 만들기 위해 필요한 최소한의 도로 건설 비용을 계산하고자 한다. 단위 도로 하나를 건설하기 위해 1 또는 2 의 비용이 소요된다고 가정하자. 위 그림에서는 흰색 단위 격자에 단위 도로 하나를 건설하기 위해서는 1 의 비용이 든다고 가정한다.

위와 같이 회색으로 표시된 단위 도로들을 4 의 비용으로 건설하면 목적을 달성할 수 있다.

도시가 위와 같이 격자 형태로 주어졌을 때 맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 가는 경로를 만들기 위해 필요한 최소 도로 건설 비용을 구하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 열의 정보를 나타내는 n개의 숫자가 주어진다. 각 열의 정보는 정수 0, 1, 2, -1 로 나타내며 0 은 단위도로가 이미 존재하는 것을, 즉, 도로에 유실이 없는 상태, 1 은 단위 도로가 없고 1 의 비용으로 도로를 건설할 수 있는 단위 격자, 2 는 단위 도로가 없고 2 의 비용으로 도로를 건설할 수 있는 단위 격자를 의미한다. -1 은 X로 표시된 단위 격자로 그 위치에 단위 도로를 건설할 수 없는 상태를 의미한다.

출력

출력은 표준출력을 사용한다. 도시의 맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 가는 경로를 만들기 위해 필요한 최소한의 도로 건설 비용을 한 줄에 출력한다. 해당 경로를 건설할 수 없을 때는 -1 을 출력한다.

---

💚나의 풀이

• 4방향으로 (0,0)부터 뻗어나가면서 (N-1, M-1) 지점의 좌표값을 출력하면 되는 다익스트라 문제이다.
• 처음부터 시작점이나 도착점이 -1로 닿을 수 없을 경우 -1 출력하도록 조건을 걸어두고
• 아닌 경우에 한해서 다익스트라 함수에 시작점을 담아 호출하고 반환받은 2차원 배열 속 dist[N-1][M-1]이 또 다시 Integer.MaxValue의 초기값을 지닌 경우 닿을 수 없는 경우이므로-1 출력하도록 걸어둔다.
• 그 상황을 제외하고는 dist[N-1][M-1] 지점의 값을 최종 출력하도록 하면 된다.
• 다익스트라 함수 안에서 초기값을 설정해줄 때, dist[x][y]의 값은 0이 아니라 최초에 map[x][y]좌표가 갖고 있던 가중치 값으로 초기화를 해주어야 한다.
• 그 외의 경우 4방향으로 뻗어가면서 map[nx][ny]가 -1이 아닌 경우에 한해서 뻗어가면 최종 최단거리가 도출된다.

package to_0901_7;

import java.util.*;

/*20046번. Road Reconstruction - 다익스트라 문풀 */
public class Main {
	static int N, M;
	static int[][] map;
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	//다익스트라 
	static int[][] dijkstra(int x, int y){
	
		int[][] distance = new int[N][M];
		for(int i=0; i<N; i++) {
			Arrays.fill(distance[i], Integer.MAX_VALUE);
		}
		PriorityQueue<int[]> pQ =new PriorityQueue<>((a, b) -> a[2] - b[2]);

		//시작점 처리 
		distance[x][y] = map[x][y];//자기 자신의 값으로 세팅 
		pQ.offer(new int[] {x, y, map[x][y]});
		
		while(!pQ.isEmpty()) {
			int[] cur = pQ.poll();
			if(cur[2] > distance[cur[0]][cur[1]]) continue;//기존값보다 크면 건너뜀
			
			for(int k=0; k<4; k++) {
				int nx = cur[0] + dx[k];
				int ny = cur[1] + dy[k];
				if(nx <0 || ny <0 || nx >= N || ny >= M) continue;
				if(map[nx][ny] == -1) continue; //-1값 갖는 경우는 그냥 넘김 
				//0, 1, 2의 값만 갖는 경우에 한해서 
				if(distance[nx][ny] > distance[cur[0]][cur[1]] + map[nx][ny]) {
					distance[nx][ny] = distance[cur[0]][cur[1]] + map[nx][ny];
					pQ.offer(new int[] {nx, ny, distance[nx][ny]});
				}
			}
		}
		
		return distance;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		
		map = new int[N][M];
		
		//데이터 입력 받기
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j] = kb.nextInt();
			}
		}
		//시작위치 or 도착 위치가 조차도 건설 불가능한 위치일 경우 
		if(map[0][0] == -1 || map[N-1][M-1] == -1) {
			System.out.println("-1");
		}else {
			int[][] dist = dijkstra(0, 0);
			
			if(dist[N-1][M-1] == Integer.MAX_VALUE) {
				System.out.println("-1");
			}else {
				System.out.println(dist[N-1][M-1]);
			}			
		}
	}
}