[프로그래머스 / Level3] 블록 이동하기 (Java)

문제 보기

사용한 것

• 도착하는 최단 시간을 구하기 위한 BFS
• 드론의 좌표, 이동 횟수, 수평 or 수직을 저장하기 위한 Drone

풀이 방법

• 드론은 2칸을 차지하니 수평, 수직일 때 메인으로할 좌표를 정한다.
  • 필자는 지도상으로 수평일 때 왼쪽 좌표, 수직일 때 위 좌표로 정했다.
• visited를 int[N][N][2]로 초기화한다.
  • 같은 좌표여도 수평인지, 수직인지에 따라 다르기 때문에 방문 시 수평이면 visited[x][y][0], 수직이면 visited[x][y][1]를 true로 만든다.
• BFS를 돌리면서 4가지 방향으로 이동, 4가지 방향으로 회전한다. (회전은 수평, 수직 상태에서 4개 씩 총 8가지 경우의 수)
  • 이동하거나 회전할 때 영역을 벗어나지 않는지, 벽이라 이동할 수 없는지 고려한다.
  • 드론은 2칸이므로 2칸 다 고려해야 하고, 회전의 경우 회전 방향에 따라 고려해줘야 한다.
  • 이미 방문 했으면 continue, 다음 드론을 q에 넣기 전에 visited 갱신
• 도착하면 드론의 depth를 answer에 저장하고 BFS를 종료한다.
• answer을 반환한다.

코드

class Solution {

    int N;
    int[][] map;
    boolean[][][] visited;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    int answer;


    public int solution(int[][] board) {
        N = board.length;
        map = board;
        visited = new boolean[N][N][2];

        bfs();

        return answer;
    }

    void bfs() {
        Queue<Drone> q = new LinkedList<>();
        visited[0][0][0] = true;
        q.offer(new Drone(0, 0, 0, true));
        while (!q.isEmpty()) {
            Drone drone = q.poll();

            // 도착
            if (isArrived(drone)) {
                answer = drone.depth;
                break;
            }

            // 이동
            for (int i = 0; i < 4; i++) {
                int nx = drone.x + dx[i];
                int ny = drone.y + dy[i];
                int type = drone.horizontal ? 0 : 1;

                if (!canMove(drone, i) || visited[nx][ny][type]) {
                    continue;
                }

                visited[nx][ny][type] = true;
                q.offer(new Drone(nx, ny, drone.depth + 1, drone.horizontal));
            }

            // 회전
            for (int i = 0; i < 4; i++) {
                int[] nextPosition = getNextPosition(drone, i);
                int nx = nextPosition[0];
                int ny = nextPosition[1];
                int type = drone.horizontal ? 1 : 0;

                if (!canRotate(drone, i) || visited[nx][ny][type]) {
                    continue;
                }

                visited[nx][ny][type] = true;
                q.offer(new Drone(nx, ny, drone.depth + 1, !drone.horizontal));
            }
        }
    }

    boolean isArrived(Drone drone) {
        if (drone.x == N - 1 && drone.y == N - 1) {
            return true;
        }
        if (drone.horizontal && drone.x == N - 1 && drone.y + 1 == N - 1) {
            return true;
        }
        if (!drone.horizontal && drone.x + 1 == N - 1 && drone.y == N - 1) {
            return true;
        }

        return false;
    }

    boolean canMove(Drone drone, int dir) {
        int nx = drone.x + dx[dir];
        int ny = drone.y + dy[dir];
        if (nx < 0 || nx >= N || ny < 0 || ny >= N || map[nx][ny] == 1) {
            return false;
        }
        if (drone.horizontal) {
            if (ny + 1 >= N || map[nx][ny + 1] == 1) {
                return false;
            }
        }
        if (!drone.horizontal) {
            if (nx + 1 >= N || map[nx + 1][ny] == 1) {
                return false;
            }
        }

        return true;
    }

    boolean canRotate(Drone drone, int dir) {
        if (drone.horizontal) {
            if (dir == 1 || dir == 2) {
                if (dir == 1) {
                    if (drone.x + 1 >= N || drone.y + 1 >= N) {
                        return false;
                    }
                } else {
                    if (drone.x + 1 >= N || drone.y >= N) {
                        return false;
                    }
                }
                if (map[drone.x + 1][drone.y + 1] == 1 || map[drone.x + 1][drone.y] == 1) {
                    return false;
                }
            } else {
                if (dir == 3) {
                    if (drone.x - 1 < 0 || drone.y + 1 >= N) {
                        return false;
                    }
                } else {
                    if (drone.x - 1 < 0) {
                        return false;
                    }
                }
                if (map[drone.x - 1][drone.y + 1] == 1 || map[drone.x - 1][drone.y] == 1) {
                    return false;
                }
            }
        } else {
            if (dir == 1 || dir == 2) {
                if (dir == 1) {
                    if (drone.y - 1 < 0) {
                        return false;
                    }
                } else {
                    if (drone.x + 1 >= N || drone.y - 1 < 0) {
                        return false;
                    }
                }
                if (map[drone.x][drone.y - 1] == 1 || map[drone.x + 1][drone.y - 1] == 1) {
                    return false;
                }
            } else {
                if (dir == 3) {
                    if (drone.y + 1 >= N) {
                        return false;
                    }
                } else {
                    if (drone.x + 1 >= N || drone.y + 1 >= N) {
                        return false;
                    }
                }
                if (map[drone.x][drone.y + 1] == 1 || map[drone.x + 1][drone.y + 1] == 1) {
                    return false;
                }
            }
        }

        return true;
    }

    int[] getNextPosition(Drone drone, int dir) {
        int nx;
        int ny;
        if (drone.horizontal) {
            if (dir == 1) {
                nx = drone.x;
                ny = drone.y;
            } else if (dir == 2) {
                nx = drone.x;
                ny = drone.y + 1;
            } else if (dir == 3) {
                nx = drone.x - 1;
                ny = drone.y;
            } else {
                nx = drone.x - 1;
                ny = drone.y + 1;
            }
        } else {
            if (dir == 1) {
                nx = drone.x;
                ny = drone.y - 1;
            } else if (dir == 2) {
                nx = drone.x + 1;
                ny = drone.y - 1;
            } else if (dir == 3) {
                nx = drone.x;
                ny = drone.y;
            } else {
                nx = drone.x + 1;
                ny = drone.y;
            }
        }

        return new int[]{nx, ny};
    }
}

class Drone {

    public int x;
    public int y;
    public int depth;
    public boolean horizontal = true;

    public Drone(int x, int y, int depth, boolean horizontal) {
        this.x = x;
        this.y = y;
        this.depth = depth;
        this.horizontal = horizontal;
    }
}