(Java) 프로그래머스 - 리코쳇 로봇

BFS  + 조건이 붙은 문제였다.

문제를 읽고 예전에 했던 게임이 생각나서 재미있게 풀었다.

---

로직

먼저 board를 순회하며 아직 계산되지 않은 노드를 INF로 초기화 하고, 시작 지점과 도착 지점의 좌표를 저장한다.

시작지점에서 BFS 탐색을 시작하는데, 다른 점은 우선순위 큐를 사용한다는 것이다.

우선순위 큐를 이용하면 상하좌우 중 지금까지 가장 적은 방문 횟수를 가진 노드를 먼저 방문하게 되기 때문이다.

상하좌우를 선택하였다면, D를 만나거나 배열에 끝에 다다를때까지 계속 같은 방향으로 진행한다.

그리고 도착한 노드에 횟수를 더해주고 계속 탐색하면 된다.

 

최종 코드

import java.util.*;

class Solution {
    static int[] dRow = {1, -1, 0, 0};
    static int[] dCol = {0, 0, 1, -1};
    static List<Integer> list;
    
    public int solution(String[] board) {
        int INF = Integer.MAX_VALUE;
		int[][] dist = new int[board.length][board[0].length()];
		int[] start = new int[2];
		int[] target = new int[2];

		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length(); j++) {
				if (board[i].charAt(j) == 'R') {
					start = new int[] {i, j};
				}

				if (board[i].charAt(j) == 'G') {
					target = new int[] {i, j};
				}

				dist[i][j] = INF;
			}
		}

		bfs(board, dist, start);

		if (dist[target[0]][target[1]] == INF) {
			return -1;
		}

		return dist[target[0]][target[1]];
    }
    
    public void bfs(String[] board, int[][] dist, int[] start) {
		PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> dist[o[0]][o[1]]));
		queue.add(start);
		dist[start[0]][start[1]] = 0;

		while (!queue.isEmpty()) {
			int[] nowPosition = queue.poll();
			int row = nowPosition[0];
			int col = nowPosition[1];

			for (int i = 0; i < 4; i++) {
				int nextRow = row;
				int nextCol = col;
				int move = 0;

				while (true) {
					int newRow = nextRow + dRow[i];
					int newCol = nextCol + dCol[i];

					if (newRow < 0 || newRow >= board.length || newCol < 0 || newCol >= board[0].length() || board[newRow].charAt(newCol) == 'D') {
						break;
					}

					nextRow = newRow;
					nextCol = newCol;
					move = 1;
				}

				if (dist[row][col] + move < dist[nextRow][nextCol]) {
					dist[nextRow][nextCol] = dist[row][col] + move;
					queue.add(new int[] {nextRow, nextCol});
				}
			}
		}
	}
}