2020 Kakao Blind - 블록 이동하기
Level: 3
Language: Java
Comment: bfs
URL: https://programmers.co.kr/learn/courses/30/lessons/60063
전체 코드: https://github.com/juhwanHeo/algorithm/blob/main/src/main/java/com/programmers/kakao2020/blind/MovingBlocks.java
테스트 코드: https://github.com/juhwanHeo/algorithm/blob/main/src/test/java/com/programmers/kakao2020/blind/MovingBlocksTest.java
0. 문제 설명
- 문제 URL 참고
1. 로직
I. Point class
- 왼쪽 날개(lRow, lCol), 오른쪽 날개(rRow, rCol) 위치
- 비용(cost)
- 모양(status) - v(vertical), h(horizontal)
II. 회전
- 현재 모양: Horizontal
- 왼쪽 회전 예시)
- 왼쪽 어느 한 군데라도 벽에 걸리면 회전 안됨
- 오른쪽 마찬가지
- 현재 모양: Vertical
- 위쪽 회전 예시)
- 위쪽 어느 한 군데라도 벽에 걸리면 회전 안됨
- 아래도 마찬가지
- 회전 성공시 현재 모양이 변경됨
- ex) v -> h, h -> v
// horizontal static int[][] hRotates = {{-1, 0, -1, 0}, {1, 0, 1, 0}}; // vertical static int[][] vRotates = {{0, -1, 0, -1}, {0, 1, 0, 1}};
II. 이동
- 이동 가능 여부
- 두 날개(왼쪽, 오른쪽)위치가 둘다 방문했으면 이동 불가
- 두 날개(왼쪽, 오른쪽)위치가 하나라도 미방문이면 이동 가능
III. 방문 기록
- 현재 모양 상태에서 이동한 위치를 기록한다.
- Vertical Vistied
- Horizontal Visited
boolean[][][] visited = new boolean[2][board.length][board[0].length]; - Test Case 3번을 예로 들면
- 현재 모양 상관 없이 방문 하면 마지막(n x m)에 도착 못하는 경로가 먼저 방문 했다면
마지막(n x m)에 방문을 못해 결과 값이 0으로 bfs가 종료됨// boolean[][] visited = new boolean[board.length][board[0].length]; // 경로: [true, true, false, true, true, true, true, true, true, true] [true, true, true, true, true, false, true, true, true, true] [false, true, true, true, false, true, true, true, true, true] [false, true, true, true, true, true, true, true, true, true] [false, true, true, true, true, true, true, true, true, true] [true, true, false, false, false, true, true, true, true, true] [true, true, true, true, false, true, true, true, true, true] [true, false, true, true, true, true, true, true, true, true] [true, true, true, true, true, true, false, false, true, false] [true, true, true, true, true, true, true, true, true, false]
- 현재 모양 상관 없이 방문 하면 마지막(n x m)에 도착 못하는 경로가 먼저 방문 했다면
2. 전체 코드
import com.coding.utils.PrintUtils;
import java.util.LinkedList;
import java.util.Queue;
/*
* @2020 kakao blind
* @TestName: 블록 이동하기
* @URL: https://programmers.co.kr/learn/courses/30/lessons/60063
*/
public class MovingBlocks {
static class Point {
int lRow, lCol, rRow, rCol, cost;
char status;
public Point(int lRow, int lCol, int rRow, int rCol, int cost, char status) {
this.lRow = lRow;
this.lCol = lCol;
this.rRow = rRow;
this.rCol = rCol;
this.cost = cost;
this.status = status;
}
@Override
public String toString() {
return "(" + lRow + ", " + lCol + ", " + rRow + ", " + rCol + ", " + cost + ", " + status + ")";
}
}
static int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
// lRow, lCol, rRow, rCol
// horizontal
static int[][] hRotates = {{-1, 0, -1, 0}, {1, 0, 1, 0}};
// vertical
static int[][] vRotates = {{0, -1, 0, -1}, {0, 1, 0, 1}};
public static int solution(int[][] board) {
return bfs(board);
}
static int bfs(int[][] board) {
int cost = 0;
Queue<Point> queue = new LinkedList<>();
// visited[horizontal: 0 | vertical: 1][row][col]
boolean[][][] visited = new boolean[2][board.length][board[0].length];
boolean[][] rotated = new boolean[board.length][board[0].length];
visited[0][0][0] = true;
visited[0][0][1] = true;
queue.offer(new Point(0, 0, 0, 1, 0, 'h'));
while (!queue.isEmpty()) {
Point current = queue.poll();
if (current.lRow == board.length - 1 && current.lCol == board[0].length - 1
|| current.rRow == board.length - 1 && current.rCol == board[0].length - 1) {
cost = current.cost;
break;
}
for (int[] dir : dirs) {
int nlRow = current.lRow + dir[0];
int nlCol = current.lCol + dir[1];
int nrRow = current.rRow + dir[0];
int nrCol = current.rCol + dir[1];
Point next = new Point(nlRow, nlCol, nrRow, nrCol, current.cost + 1, current.status);
if (canMove(next, board, visited)) {
queue.offer(next);
if (next.status == 'h') {
visited[0][nlRow][nlCol] = true;
visited[0][nrRow][nrCol] = true;
}
else {
visited[1][nlRow][nlCol] = true;
visited[1][nrRow][nrCol] = true;
}
}
}
if (rotated[current.lRow][current.lCol] && rotated[current.rRow][current.rCol]) continue;
for (int[] rotate : current.status == 'h' ? hRotates : vRotates) {
int nlRow = current.lRow + rotate[0];
int nlCol = current.lCol + rotate[1];
int nrRow = current.rRow + rotate[2];
int nrCol = current.rCol + rotate[3];
Point next = new Point(nlRow, nlCol, nrRow, nrCol, current.cost + 1, current.status);
if (canRotate(next, board)) {
char nStatus = current.status == 'h' ? 'v' : 'h';
queue.offer(new Point(current.lRow, current.lCol, nlRow, nlCol, current.cost + 1, nStatus));
queue.offer(new Point(nrRow, nrCol, current.rRow, current.rCol, current.cost + 1, nStatus));
rotated[current.lRow][current.lCol] = true;
rotated[current.rRow][current.rCol] = true;
}
}
}
return cost;
}
/*
* map 크기 안에 있는지 확인
* */
static boolean isOk(Point moved, int[][] map) {
return moved.lRow >= 0 && moved.lRow < map.length
&& moved.rRow >= 0 && moved.rRow < map.length
&& moved.lCol >= 0 && moved.lCol < map[0].length
&& moved.rCol >= 0 && moved.rCol < map[0].length
;
}
/*
* 이동 가능 여부
* */
static boolean canMove(Point moved, int[][] map, boolean[][][] visited) {
int type = (moved.status == 'h') ? 0 : 1;
return isOk(moved, map)
&& (!visited[type][moved.lRow][moved.lCol] || !visited[type][moved.rRow][moved.rCol])
&& map[moved.lRow][moved.lCol] == 0
&& map[moved.rRow][moved.rCol] == 0
;
}
/*
* 회전 가능 여부
* */
static boolean canRotate(Point moved, int[][] map) {
return isOk(moved, map)
&& map[moved.lRow][moved.lCol] == 0
&& map[moved.rRow][moved.rCol] == 0
;
}
}
후기
2칸을 차지하고 있고, 회전, 이동 가능 여부, 현재 모양 등을
잘 판단해야 풀 수 있는 문제
Junior BE Developer