[Algorithm] 백준 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은 친구, *는 주난, #는 범인을 뜻한다.

 

[ 출력 ]

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

 

---

두 가지 이유로 오답으로 채점되었는데 이유를 알기 까지 오래걸렸습니다.

 

첫번째,

bfs를 사용해서 오답이었는데, 그 이유는

특정 위치에 대해서 time 값이 다른 Point 객체로 Queue에 삽입될 수 있는데

이를 고려해주지 않았기 때문입니다.

 

Queue는 선입선출 방식이기 때문에

만약, new Point(1, 1, 2)가 삽입된 후에 new Point(1, 1, 1)이 삽입되면

먼저 삽입된 new Point(1, 1, 2)가 먼저 추출되어

time 최솟값이 아닌 값으로 범인의 위치에 먼저 도달할 수 있습니다.

따라서 우선순위를 고려하여 추출하는 PriorityQueue를 사용해야 합니다.

 

 

두번째,

PriorityQueue에 Point 객체를 삽입할 때 

map 배열값이 '1'인 경우에 cur.time+1 값을, 그 외의 경우에는 cur.time 값을 설정했습니다.

하지만 '#'인 경우(범인의 위치)에도 cur.time+1 값으로 설정되어야 하는데 cur.time 값으로 설정되었습니다.

 

import java.io.*;
import java.util.*;

public class Main {
	
	public static class Point implements Comparable<Point> {
		int row, column, time;
		public Point(int row, int column, int time) {
			this.row = row;
			this.column = column;
			this.time = time;
		}
		public int compareTo(Point o) {
			return this.time - o.time;
		}
	}
	
    
	static int N, M, curR, curC, thiefR, thiefC;
	static char[][] map;
	static int[][] D = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken()); // 교실의 세로 크기
		M = Integer.parseInt(st.nextToken()); // 교실의 가로 크기
		map = new char[N+1][M+1];
		
		st = new StringTokenizer(br.readLine());
		curR = Integer.parseInt(st.nextToken()); // 주난이의 위치(행)
		curC = Integer.parseInt(st.nextToken()); // 주난이의 위치(열)
		thiefR = Integer.parseInt(st.nextToken()); // 범인의 위치(행)
		thiefC = Integer.parseInt(st.nextToken()); // 범인의 위치(열)
		
		for(int n = 1; n <= N; n++) {
			String input = br.readLine();
			for(int m = 1; m <= M; m++)
				map[n][m] = input.charAt(m-1); // *:주난, #:초코바, 1:친구, 0:빈공간
		}
		
		dijkstra();
	}
	
    
	public static void dijkstra() {
		PriorityQueue<Point> pq = new PriorityQueue<>();
		boolean[][] checked = new boolean[N+1][M+1];
		
		pq.offer(new Point(curR, curC, 0));
		checked[curR][curC] = true;
		
		while(!pq.isEmpty()) {
			Point cur = pq.poll();
			
			if(cur.row==thiefR && cur.column==thiefC) {
				System.out.println(cur.time);
				return;
			}
			
			for(int d = 0; d < 4; d++) {
				int nextR = cur.row + D[d][0];
				int nextC = cur.column + D[d][1];
				
				if(nextR<=0 || nextR>N || nextC<=0 || nextC>M || checked[nextR][nextC]) continue;
				
				checked[nextR][nextC] = true;
				
				pq.offer(new Point(nextR, nextC, map[nextR][nextC]=='0' ? cur.time : cur.time+1));
			}
		}
	}
}