728x90
반응형
⬛ 문제
https://programmers.co.kr/learn/courses/30/lessons/60063
⬛ 풀이
BFS 심화 문제였다.
기존 BFS 문제들은 좌표 하나를 가지고 탐색을 하지만 이번 문제는 두 좌표를 가지고 탐색을 하는 문제였다.
또한 로봇은 가로 or 세로 타입을 가지기 때문에 방문탐색은 3차원 배열 boolean[2][][]을 통해 관리하였다. visited 배열에서 각 타입별로 체크할 때 두 좌표가 모두 방문을 했을 때만 방문했었다고 판단하고, 하나라도 방문하지 않은 점을 가지면 진행할 수 있다.
4방 탐색을 할 때 최대 3가지 좌표를 큐에 삽입할 수 있다.
예를 들어 현재 좌표가 (r1, c1), (r2, c2), 로봇의 타입이 가로(0)이고, 탐색 방향 d = 0, 1(하, 상)일 때 아래 3가지 경우가 가능하다.
1. 방향전환을 하지 않은 (nr1, nc1), (nr2, nc2)
2. 첫 번째 좌표를 축으로 회전한 (r1, c1), (nr1, nc1)
3. 두 번째 좌표를 축으로 회전한 (r2, c2), nr2, nc2)
마찬가지로 로봇의 타입이 세로(1)이고, 탐색 방향 d = 2, 3(좌, 우)일 때도 최대 3가지 경우가 가능하다.
프로그램 전체 로직은 다음과 같다.
1. 최소 시간을 구하는 문제이므로 BFS로 해결하였다.
2. 가로, 세로 2가지 형태로 이동하므로 3차원 boolean[2][][]로 방문체크를 한다.
3. 2개의 좌표값을 가지고 이동하기 때문에 한 점이라도 방문하지 않은 곳이면 진행이 가능하다.
4. 큐에 상하좌우로 이동한 좌표값과 회전 가능한 좌표값을 넣어주고 끝점에 도달하면 종료한다.
⬛ 코드
import java.util.*;
public class Solution {
public int solution(int[][] board) {
int n = board.length;
int answer = 0;
boolean[][][] visited = new boolean[2][n][n]; // 0: 가로, 1: 세로
int[] dr = { -1, 1, 0, 0 }; // 하, 상, 좌, 우
int[] dc = { 0, 0, -1, 1 };
int[][] start = new int[][] { { 0, 0 }, { 0, 1 }, { 0 } }; // 2개의 좌표값과 소요시간
Queue<int[][]> q = new ArrayDeque<>();
q.offer(start);
visited[0][0][0] = true;
visited[0][0][1] = true;
// BFS
while (!q.isEmpty()) {
int[][] cur = q.poll();
int r1 = cur[0][0];
int c1 = cur[0][1];
int r2 = cur[1][0];
int c2 = cur[1][1];
int type = type(cur[0], cur[1]);
int time = cur[2][0];
if ((r1 == n - 1 && c1 == n - 1) || (r2 == n - 1 && c2 == n - 1)) {
answer = time;
break;
}
for (int d = 0; d < 4; d++) {
int nr1 = r1 + dr[d];
int nc1 = c1 + dc[d];
int nr2 = r2 + dr[d];
int nc2 = c2 + dc[d];
if (oob(nr1, nc1, n) && oob(nr2, nc2, n) && board[nr1][nc1] != 1 && board[nr2][nc2] != 1) {
// 로봇을 방향전환 없이 상하좌우 추가
if ((!visited[type][nr1][nc1] || !visited[type][nr2][nc2])) {
visited[type][nr1][nc1] = true;
visited[type][nr2][nc2] = true;
q.offer(new int[][] { { nr1, nc1 }, { nr2, nc2 }, { time + 1 } });
}
// 로봇이 가로이면서 방향이 상하 or 세로이면서 좌우일 때 회전 가능
int typeChange = 1 ^ type;
if ((type == 0 && d < 2) || (type == 1 && d > 1)) {
if (!visited[typeChange][nr1][nc1] || !visited[typeChange][r1][c1]) {
visited[typeChange][nr1][nc1] = true;
visited[typeChange][r1][c1] = true;
q.offer(new int[][] { { nr1, nc1 }, { r1, c1 }, { time + 1 } });
}
if (!visited[typeChange][nr2][nc2] || !visited[typeChange][r2][c2]) {
visited[typeChange][nr2][nc2] = true;
visited[typeChange][r2][c2] = true;
q.offer(new int[][] { { nr2, nc2 }, { r2, c2 }, { time + 1 } });
}
}
}
}
}
return answer;
}
public boolean oob(int r, int c, int n) {
return 0 <= r && r < n && 0 <= c && c < n;
}
// 두 좌표가 가로이면 0, 세로이면 1 반환
public int type(int[] pos1, int[] pos2) {
if (pos1[0] == pos2[0])
return 0;
return 1;
}
}
728x90
반응형
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 72415번 - 카드 짝 맞추기 (Java) (0) | 2021.10.23 |
---|---|
[프로그래머스] 67259번 - 경주로 건설 (Java) (0) | 2021.10.23 |
[프로그래머스] 64062번 - 징검다리 건너기 (Java) (0) | 2021.09.24 |
[프로그래머스] 42891번 - 무지의 먹방 라이브 (Java) (0) | 2021.09.15 |