백준 | 14497번. 주난의 난 - 다익스트라

⬛ 백준 14497번. 주난의 난 - 다익스트라

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

14497번: 주난의 난(難)

문제

주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다.

‘쿵... 쿵...’

주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 N×M크기의 학교 교실 어딘가에서 뛰기 시작했다. 주난이의 파동은 상하좌우 4방향으로 친구들을 쓰러뜨릴(?) 때 까지 계속해서 퍼져나간다. 다르게 표현해서, 한 번의 점프는 한 겹의 친구들을 쓰러뜨린다. 다음의 예를 보자.

1 # 1 0 1 1 1
1 1 0 1 0 0 1
0 0 1 * 1 1 1
1 1 0 1 1 1 1
0 0 1 1 0 0 1

주난이를 뜻하는 *은 (3, 4)에 있고, 초코바를 가진 학생 #는 (1, 2)에 있다. 0은 장애물이 없는 빈 공간임을 뜻하고, 1은 친구들이 서있음을 의미한다. 다음은 주난이의 점프에 따른 생존(?) 학생들의 변화이다.

1 # 1 0 1 1 1
1 1 0 0 0 0 1
0 0 0 * 0 1 1
1 1 0 0 1 1 1
0 0 1 1 0 0 1

1 # 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 * 0 0 1
0 0 0 0 0 1 1
0 0 0 0 0 0 1

0 X 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 * 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

위의 예시에서 주난이는 3번의 점프 만에 초코바를 훔쳐간 범인을 찾아낼 수 있다!

주난이를 빨리 멈춰야 교실의 안녕을 도모할 수 있다. 주난이에게 최소 점프 횟수를 알려줘서 교실을 지키자.

입력

첫째 줄에 주난이가 위치한 교실의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 300)

둘째 줄에 주난이의 위치 x1, y1과 범인의 위치 x2, y2가 주어진다. (1 ≤ x1, x2 ≤ N, 1 ≤ y1, y2 ≤ M)

이후 N×M 크기의 교실 정보가 주어진다. 0은 빈 공간, 1은 친구, *는 주난, #는 범인을 뜻한다.

출력

주난이가 범인을 잡기 위해 최소 몇 번의 점프를 해야 하는지 출력한다.

---

💚나의 풀이

• 주난이의 위치를 시작점으로 하고, 범인의 위치를 도착점으로 한다.
• 그리고 입력을 받을 때는 두 위치 모두 0으로 세팅해준다.
• 다익스트라로 4방향을 뻗어갈 때, 최대한 장애물 안만나게 0으로 뻗어가겠지만, 1을 만나면 최소한의 개수로 만나도록 세팅을 한다.
• 범인의 위치 좌표를 pQ에서 뽑게 되면 그냥 거기서 return 한다.
• 최종 답 처리할 땐 dist[][]의 범인 위치값에 + 1 처리를 해야 정답이 나온다.

package to_0901_8;

import java.util.*;
import java.util.PriorityQueue;
import java.util.Scanner;

/*14497번. 주난의 난 - 다익스트라 */
public class Main {

	static int N, M;
	static int x1, y1, x2, y2;
	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[][] dist = new int[N][M];
		for(int i=0; i<N; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
		
		PriorityQueue<int[]> pQ = new PriorityQueue<>((a, b) -> a[2]-b[2]);
		dist[x][y] = 0;
		pQ.offer(new int[] {x, y, 0});
		
		while(!pQ.isEmpty()) {
			int[] cur = pQ.poll();
			if(cur[2] > dist[cur[0]][cur[1]]) continue;
			
			if(cur[0]==x2-1 && cur[1] == y2-1) {
				return dist;//여기서 그냥 넘겨줘도 됨 
			}
			
			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(dist[nx][ny] > dist[cur[0]][cur[1]] + map[nx][ny]) {
					dist[nx][ny] = dist[cur[0]][cur[1]] + map[nx][ny];
					pQ.offer(new int[] {nx, ny, dist[nx][ny]});
				}
			}
		}
		return dist;
	}
	
	//main 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		x1 = kb.nextInt();
		y1 = kb.nextInt();
		x2 = kb.nextInt();
		y2 = kb.nextInt();
		
		map = new int[N][M];
		
		for(int i=0; i<N; i++) {
			String tmp = kb.next();
			
			for(int j=0; j<M; j++) {
				if(tmp.charAt(j) == '#') {
					map[i][j] = 0;
				}else if(tmp.charAt(j) == '*') {
					map[i][j] = 0;
				}else {
					map[i][j] = Character.getNumericValue(tmp.charAt(j));
				}
			}
		}
		
		int[][] dist1 = dijkstra(x1-1, y1-1);
		
		System.out.println(dist1[x2-1][y2-1] + 1);
		
	}

}