주어진 보드에 시작지점, 장애물, 목표지점이 표기돼있으며 이동은 sliding으로만 가능합니다. 이때 목표지점에 도달하는 최소 sliding 횟수를 구하는 문제입니다. 최소 횟수를 구해야하므로 bfs
가 제격입니다.
먼저 addQueueR
method로 시작지점의 좌표를 queue에 넣어 탐색을 시작합니다.
목표지점에 도달할 수 없는 경우를 판별하기 위해 visited
array를 만들어 방문여부를 판별합니다. 이 때, 직전에 어디서부터 현재지점
으로 sliding 해왔는 지는 다음 sliding 지점에 영향을 주지 않습니다. 현재지점
엔 다시 올 필요가 없으니 무조건 현재지점
을 바로 방문처리 하면 되고, 더이상 방문할 수 있는 곳이 없어지면 목표지점에 도달할 수 없는 겁니다.
sliding을 구현하느라 코드가 너무 길어서 줄여본다고 줄였는데 쉽지 않네요.
import java.util.*;
class Solution {
Queue<int[]> queue = new LinkedList<>();
public int solution(String[] board) {
boolean[][] visited = new boolean[board.length][board[0].length()];
addQueueR(board);
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int r = cur[0];
int c = cur[1];
int step = cur[2];
if (visited[r][c] == true) {
continue;
}
visited[r][c] = true;
if (board[r].charAt(c) == 'G') {
return step;
}
bfs(board, visited, cur);
}
return -1;
}
public void bfs(String[] board, boolean[][] visited, int[] cur) {
int step = cur[2];
int sr;
int sc;
// slide Down
sr = cur[0];
sc = cur[1];
while (sr != board.length && board[sr].charAt(sc) != 'D') {
sr++;
}
if (visited[--sr][sc] == false) {
queue.add(new int[] {sr, sc, step + 1});
}
// slide Up
sr = cur[0];
sc = cur[1];
while (sr != -1 && board[sr].charAt(sc) != 'D') {
sr--;
}
if (visited[++sr][sc] == false) {
queue.add(new int[] {sr, sc, step + 1});
}
// slide Right
sr = cur[0];
sc = cur[1];
while (sc != board[0].length() && board[sr].charAt(sc) != 'D') {
sc++;
}
if (visited[sr][--sc] == false) {
queue.add(new int[] {sr, sc, step + 1});
}
// slide Left
sr = cur[0];
sc = cur[1];
while (sc != -1 && board[sr].charAt(sc) != 'D') {
sc--;
}
if (visited[sr][++sc] == false) {
queue.add(new int[] {sr, sc, step + 1});
}
}
public void addQueueR(String[] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length(); j++) {
if (board[i].charAt(j) == 'R') {
queue.add(new int[] {i, j, 0});
return;
}
}
}
}
}