import java.util.*;
class Node {
private int pos1X;
private int pos1Y;
private int pos2X;
private int pos2Y;
private int distance;
public int getPos1X() {
return this.pos1X;
}
public int getPos1Y() {
return this.pos1Y;
}
public int getPos2X() {
return this.pos2X;
}
public int getPos2Y() {
return this.pos2Y;
}
public int getDistance() {
return this.distance;
}
public Node(int pos1X, int pos1Y, int pos2X, int pos2Y, int distance) {
this.pos1X = pos1X;
this.pos1Y = pos1Y;
this.pos2X = pos2X;
this.pos2Y = pos2Y;
this.distance = distance;
}
}
class Solution {
public ArrayList getNextPos(Node pos, int[][] board) {
// 반환 결과(이동 가능한 위치들)
ArrayList nextPos = new ArrayList();
// (상, 하, 좌, 우)로 이동하는 경우에 대해서 처리
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
int pos1NextX = pos.getPos1X() + dx[i];
int pos1NextY = pos.getPos1Y() + dy[i];
int pos2NextX = pos.getPos2X() + dx[i];
int pos2NextY = pos.getPos2Y() + dy[i];
int distanceNext = pos.getDistance() + 1;
// 이동하고자 하는 두 칸이 모두 비어 있다면
if (board[pos1NextX][pos1NextY] == 0 && board[pos2NextX][pos2NextY] == 0) {
nextPos.add(new Node(pos1NextX, pos1NextY, pos2NextX, pos2NextY, distanceNext));
}
}
// 현재 로봇이 가로로 놓여 있는 경우
int[] hor = {-1, 1};
if (pos.getPos1X() == pos.getPos2X()) {
for (int i = 0; i < 2; i++) { // 위쪽으로 회전하거나, 아래쪽으로 회전
// 위쪽 혹은 아래쪽 두 칸이 모두 비어 있다면
if (board[pos.getPos1X() + hor[i]][pos.getPos1Y()] == 0 && board[pos.getPos2X() + hor[i]][pos.getPos2Y()] == 0) {
nextPos.add(new Node(pos.getPos1X(), pos.getPos1Y(), pos.getPos1X() + hor[i], pos.getPos1Y(), pos.getDistance() + 1));
nextPos.add(new Node(pos.getPos2X(), pos.getPos2Y(), pos.getPos2X() + hor[i], pos.getPos2Y(), pos.getDistance() + 1));
}
}
}
// 현재 로봇이 세로로 놓여 있는 경우
int[] ver = {-1, 1};
if (pos.getPos1Y() == pos.getPos2Y()) {
for (int i = 0; i < 2; i++) { // 왼쪽으로 회전하거나, 오른쪽으로 회전
// 왼쪽 혹은 오른쪽 두 칸이 모두 비어 있다면
if (board[pos.getPos1X()][pos.getPos1Y() + ver[i]] == 0 && board[pos.getPos2X()][pos.getPos2Y() + ver[i]] == 0) {
nextPos.add(new Node(pos.getPos1X(), pos.getPos1Y(), pos.getPos1X(), pos.getPos1Y() + ver[i], pos.getDistance() + 1));
nextPos.add(new Node(pos.getPos2X(), pos.getPos2Y(), pos.getPos2X(), pos.getPos2Y() + ver[i], pos.getDistance() + 1));
}
}
}
// 현재 위치에서 이동할 수 있는 위치를 반환
return nextPos;
}
public int solution(int[][] board) {
// 맵 외곽에 벽을 두는 형태로 맵 변형
int n = board.length;
int[][] newBoard = new int[n + 2][n + 2];
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
newBoard[i][j] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
newBoard[i + 1][j + 1] = board[i][j];
}
}
// 너비 우선 탐색(BFS) 수행
Queue q = new LinkedList<>();
ArrayList visited = new ArrayList<>();
Node pos = new Node(1, 1, 1, 2, 0); // 시작 위치 설정
q.offer(pos); // 큐에 삽입한 뒤에
visited.add(pos); // 방문 처리
// 큐가 빌 때까지 반복
while (!q.isEmpty()) {
pos = q.poll();
// (n, n) 위치에 로봇이 도달했다면, 최단 거리이므로 반환
if ((pos.getPos1X() == n && pos.getPos1Y() == n) || (pos.getPos2X() == n && pos.getPos2Y() == n)) {
return pos.getDistance();
}
// 현재 위치에서 이동할 수 있는 위치 확인
ArrayList nextPos = getNextPos(pos, newBoard);
for (int i = 0; i < nextPos.size(); i++) {
// 아직 방문하지 않은 위치라면 큐에 삽입하고 방문 처리
boolean check = true;
pos = nextPos.get(i);
for (int j = 0; j < visited.size(); j++) {
if (pos.getPos1X() == visited.get(j).getPos1X() && pos.getPos1Y() == visited.get(j).getPos1Y() && pos.getPos2X() == visited.get(j).getPos2X() && pos.getPos2Y() == visited.get(j).getPos2Y()) {
check = false;
break;
}
}
if (check) {
q.offer(pos);
visited.add(pos);
}
}
}
return 0;
}
}