priority queue

📌 문제 : 이런이런, 오늘은 어떤 금쪽이를 먼저 만날까?

N × M 크기의 상담센터에서 육은영 선생님이 시작점 S에서 금쪽이를 찾아가 상담하려고 한다.

육은영 선생님은 상하좌우로 이동할 수 있으며, 각 금쪽이는 1~9의 상담 우선순위를 가진다.
숫자가 작을수록 상담 우선순위가 높다.

육은영 선생님은 다음 순서에 따라 가장 먼저 상담할 금쪽이를 선택한다.

1. 거리가 짧은 금쪽이
2. 거리가 같으면 상담 우선순위가 높은 금쪽이
3. 우선순위도 같으면 행 번호가 작은 위치의 금쪽이
4. 행 번호도 같으면 열 번호가 작은 위치의 금쪽이

선택한 금쪽이의 [우선순위, 행, 열, 거리]를 출력한다.

도달할 수 있는 금쪽이가 없다면 -1을 출력한다.

🔎 조건

2 <= N, M <= 100

금쪽이의 상담 우선순위는 1 이상 9 이하이다.

육은영 선생님은 상, 하, 좌, 우로만 이동할 수 있다.

S는 육은영 선생님의 시작점이다.

.은 이동 가능한 공간이다.

#은 이동할 수 없는 벽이다.

같은 상담 우선순위를 가진 금쪽이가 여러 명 존재할 수 있다.

testcase-1

6 7
S..#...
.#.#.2.
.#.#...
.#.....
.#####.
......1

# output-1

[2, 1, 5, 10]

testcase-2

5 7
.......
...3...
.......
...S..1
.......

# output-2

[3, 1, 3, 2]

testcase-3

5 7
.......
...2...
.......
1..S...
.......

# output-3

[1, 3, 0, 3]

testcase-4

7 7
.......
...1...
.......
...S...
.......
...1...
.......

# output-4

[1, 1, 3, 2]

testcase-5

5 9
.........
.........
.1..S..1.
.........
.........

# output-5

[1, 2, 1, 3]

testcase-6

7 7
.......
.1#....
..#....
S.#..2.
..#....
.......
.......

# output-6

[1, 1, 1, 3]

testcase-7

5 7
S..#..1
...#...
...#...
...#...
...#..2

# output-7

-1

🙋‍♂️ 들어가며

우선순위를 생각하여 조건을 배치하고, 예외처리가 필요한 문제다.

✅ 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;


// pq
import java.util.PriorityQueue;

// bfs
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Arrays;



public class Solution {
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] row_col = br.readLine().split(" ");
		int row = Integer.parseInt(row_col[0]);
		int col = Integer.parseInt(row_col[1]);
		
		
		// 1. 시작행, 시작열 찾기
		int sr = -1;
		int sc = -1;
		
		char[][] arr = new char[row][col];
		for (int r = 0; r < row; r++) {
			String cols = br.readLine();
			for (int c = 0; c < col; c++) {
				arr[r][c] = cols.charAt(c);
				if (arr[r][c] == 'S') {
					sr = r;
					sc = c;
				}
			}
		}
		
		// 3. 탐색
		lets_find(arr, sr, sc, row, col);
	}
	
	// 2. 함수 (lets_find)
	static void lets_find(char[][] arr, int sr, int sc, int row, int col) {
		
		// 2-1. pq 선언
		PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> {
			
			// 2-1-a. 거리가 다르다면, 거리 짧은순
			if (a[3] != b[3]) {
				return Integer.compare(a[3], b[3]);
			}
			
			// 2-1-b. 거리는 같지만, 고객 우선순위가 다르면, 고객우선순위 작은순
			if (a[0] != b[0]) {
				return Integer.compare(a[0], b[0]);
			}
			
			// 2-1-c. 고객우선순위가 같지만, 행이 다르다면, 행 작은순
			if (a[1] != b[1]) {
				return Integer.compare(a[1], b[1]);
			}
			
			// 2-1-d. 행도 같다면 열 작은순
			return Integer.compare(a[2], b[2]);
		});
		
		
		// 2-2. q선언하고 초기값 삽입후 visited 처리
		boolean[][] visited = new boolean[row][col];
		Queue<int[]> q = new ArrayDeque<>();
		int s_dist = 0;
		q.add(new int[] {sr, sc, s_dist});
		visited[sr][sc] = true;
		
		// 2-3. 검사
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int cr = cur[0];
			int cc = cur[1];
			int c_dist = cur[2];
			
			// 2-4. 고객번호인지 아닌지 검사
			if (arr[cr][cc] != 'S' && arr[cr][cc] - '0' >= 1 && arr[cr][cc] -'0' <= 9) {
				int c_no = arr[cr][cc] - '0';
				pq.add(new int[] {c_no, cr, cc, c_dist});
			}
			
			// 2-5. 4방향
			for (int d = 0; d < 4; d++) {
				int nr = cr + dr[d];
				int nc = cc + dc[d];
				
				// 2-6. 범위 밖이면 skip
				if (nr < 0 || nr >= row || nc < 0 || nc >= col) continue;
				
				// 2-7. 범위 안이지만 못지나가면 skip
				if (arr[nr][nc] == '#') continue;
				
				// 2-8. 지나갈 수 있지만, 방문했다면 skip
				if (visited[nr][nc]) continue;
				
				// 2-9. 방문도 안했고, 안전한 좌표면?
				visited[nr][nc] = true;
				int n_dist = c_dist + 1;
				q.add(new int[] {nr, nc, n_dist});
			}
		}
		
		// 2-10. 조기종료
		if (pq.size() == 0) {
			System.out.println(-1);
			return;
		}
		
		// 2-11. 추출
		int size = pq.size();
		for (int i = 0; i < size; i++) {
			int[] cur = pq.poll();
			System.out.println(Arrays.toString(cur));
			break;
		}
		
		
		// 2-12. 종료
		return;
	}
}