프로그래머스 코딩테스트 연습 - 블록 이동하기 (BFS, 카카오 채용)

# 주소

https://school.programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

# 문제

• 블록 이동하기

문제 설명

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

---

입출력 예

boardresult

[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]

7

입출력 예에 대한 설명

문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

# 문제 해설 및 코드 리뷰

import java.util.LinkedList;
import java.util.Queue;
class Point{
    int x1;
    int y1;
    int x2;
    int y2;
    int time;
    Point(int x1, int y1, int x2, int y2, int time){
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        this.time = time;
    }
}
class Solution {
    static int answer = Integer.MAX_VALUE;
    static int[][] arr;
    static int[][] dir2 = {{0, 0}, {0, 0}, {0, 1}, {0, -1}};
    static int[][] dir = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    static int[][] move = {{1,-1},{-1,-1},{-1,1},{1,1}};
    static int[][] move2 = {{1,1},{-1,1},{1,1},{1,-1}};
    static int[][] move3 = {{1,-1},{-1,-1},{-1,1},{-1,-1}};
    static Queue<Point> queue = new LinkedList<>();
    static boolean[][][][] visit;
    public int solution(int[][] board) {
        arr = board;
        visit = new boolean[arr.length][arr.length][arr.length][arr.length];
        visit[0][0][0][1] = true;
        queue.offer(new Point(0, 0, 0, 1, 0));
        bfs();
        return answer;
    }
    static void bfs(){
        while(!queue.isEmpty()){
            Point now = queue.poll();
            if((now.x1 == arr.length - 1 && now.y1 == arr.length - 1)
            || (now.x2 == arr.length - 1 && now.y2 == arr.length - 1))
                answer = Math.min(answer, now.time);
            for(int i = 0; i < 8; i++){
                if(i >= 4){
                    dfs(i, now);
                    continue;
                }
                int nx1 = now.x1 + dir[i][0];
                int ny1 = now.y1 + dir[i][1];
                int nx2 = now.x2 + dir[i][0];
                int ny2 = now.y2 + dir[i][1];
                if(nx1 < 0 || ny1 < 0 || nx1 >= arr.length || ny1 >= arr.length)
                    continue;
                if(nx2 < 0 || ny2 < 0 || nx2 >= arr.length || ny2 >= arr.length)
                    continue;
                if(visit[nx1][ny1][nx2][ny2])
                    continue;
                if(arr[nx1][ny1] == 1 || arr[nx2][ny2] == 1)
                    continue;
                queue.offer(new Point(nx1, ny1, nx2, ny2, now.time + 1));
                visit[nx1][ny1][nx2][ny2] =  true;
            }
        }
    }
    static void dfs(int t, Point now){
        if(now.x1 == now.x2 && t == 4) {
            if(now.y1 > now.y2){
                int temp = now.y2;
                now.y2 = now.y1;
                now.y1 = temp;
            }
            //x2, y2 이동(가로모양일 때 오른쪽에 있는)
            for (int i = 0; i < 2; i++) {
                int nx = now.x2 + move[i][0];
                int ny = now.y2 + move[i][1];
                int mx = now.x2 + dir[i][0];
                int my = now.y2 + dir[i][1];
                if(mx < 0 || my < 0 || mx >= arr.length || my >= arr.length)
                    continue;
                if(arr[mx][my] == 1)
                    continue;
                if (nx < 0 || ny < 0 || nx >= arr.length || ny >= arr.length)
                    continue;
                if (visit[now.x1][now.y1][nx][ny])
                    continue;
                if (arr[nx][ny] == 1)
                    continue;
                queue.offer(new Point(now.x1, now.y1, nx, ny, now.time + 1));
                visit[now.x1][now.y1][nx][ny] = true;
            }
        }else if(now.x1 == now.x2 && t == 5){//가로모양일 때 왼쪽에 있는 x1, y1 이동
            if(now.y1 > now.y2){
                int temp = now.y2;
                now.y2 = now.y1;
                now.y1 = temp;
            }
            for (int i = 0; i < 2; i++) {
                int nx = now.x1 + move2[i][0];
                int ny = now.y1 + move2[i][1];
                int mx = now.x1 + dir[i][0];
                int my = now.y1 + dir[i][1];
                if(mx < 0 || my < 0 || mx >= arr.length || my >= arr.length)
                    continue;
                if(arr[mx][my] == 1)
                    continue;
                if (nx < 0 || ny < 0 || nx >= arr.length || ny >= arr.length)
                    continue;
                if (visit[nx][ny][now.x2][now.y2])
                    continue;
                if (arr[nx][ny] == 1)
                    continue;
                queue.offer(new Point(nx, ny, now.x2, now.y2, now.time + 1));
                visit[nx][ny][now.x2][now.y2] =  true;
            }
        }else if(now.y1 == now.y2 && t == 6){ //세로 모양일 때 위에 있는 x1, y1 이동
            if(now.x1 > now.x2){
                int temp = now.x2;
                now.x2 = now.x1;
                now.x1 = temp;
            }
            for (int i = 2; i < 4; i++) {
                int nx = now.x1 + move2[i][0];
                int ny = now.y1 + move2[i][1];
                int mx = now.x1 + dir2[i][0];
                int my = now.y1 + dir2[i][1];
                if(mx < 0 || my < 0 || mx >= arr.length || my >= arr.length)
                    continue;
                if(arr[mx][my] == 1)
                    continue;
                if (nx < 0 || ny < 0 || nx >= arr.length || ny >= arr.length)
                    continue;
                if (visit[nx][ny][now.x2][now.y2])
                    continue;
                if (arr[nx][ny] == 1)
                    continue;
                queue.offer(new Point(nx, ny, now.x2, now.y2, now.time + 1));
                visit[nx][ny][now.x2][now.y2] =  true;
            }
        }else if(now.y1 == now.y2 && t == 7){ //세로 모양일 때 아래에 있는 x2, y2 이동
            if(now.x1 > now.x2){
                int temp = now.x2;
                now.x2 = now.x1;
                now.x1 = temp;
            }
            for (int i = 2; i < 4; i++) {
                int nx = now.x2 + move3[i][0];
                int ny = now.y2 + move3[i][1];
                int mx = now.x2 + dir2[i][0];
                int my = now.y2 + dir2[i][1];
                if(mx < 0 || my < 0 || mx >= arr.length || my >= arr.length)
                    continue;
                if(arr[mx][my] == 1)
                    continue;
                if (nx < 0 || ny < 0 || nx >= arr.length || ny >= arr.length)
                    continue;
                if (visit[now.x1][now.y1][nx][ny])
                    continue;
                if (arr[nx][ny] == 1)
                    continue;
                queue.offer(new Point(now.x1, now.y1, nx, ny, now.time + 1));
                visit[now.x1][now.y1][nx][ny] =  true;
            }
        }
    }
}

여러분 제가 카카오 기출 문제 푼 것 중에서 이 문제만큼 100% 제 힘으로 푼건 몇 개 없어요.

찾아보니까 정답률 1.4% 문제던데 푸는데 기간으로는 하루가 걸렸고 시간으로 따지면 5시간 정도 투자했습니다.

첫 날에 세시간 정도 이걸 짜면서 왜 안되지 고민하면서 자다가 문득 아 ~~해서 짜보면 정답 되겠는데? 싶어서 다음날 적용시키니 진짜 풀려서 신기했습니다.

이렇게 코드가 방대하고 대책없이 짜면 시간초과나는게 정상인데 이건 정답이 되네요?

음.. 왜 그런지 한 번 살펴봅시다.

부끄럽지만 이렇게 작성했어도 정답 코드입니다 ㅋㅋㅋㅋ.....

 

이 문제를 이해하려면 BFS에 대해 어느정도 이해하고 계셔야 합니다.

BFS란 넓이 우선 탐색의 약자로서 코딩테스트에 자주 나오는 문제 유형입니다.

이 문제는 까다로운 점이, 2개의 점을 같이 이동시켜야 한다는 점인데요.

또한 회전을 할 수 있으며 덩달아 이동도 할 수 있을 때 목표 지점 도달을 위한 최소 시간을 리턴하는 것이 정답이 되어야 합니다.

하나의 점에 대해서는 재방문을 해도 되지만 2개의 점이 묶여있을 때 재방문을 막아야 재탐색이 이루어지지 않기 때문에 처음에 이걸 가지고 어떻게 해야하나 고민을 많이 했습니다.

visit배열을 보통은 2차원으로 쓰기 마련인데 저는 혹시나 하는 마음에 4차원으로 선언해서 써봤더니 진짜 정답이 되네요?

어떤 분들은 HashMap을 쓰던데 저는 이상하게 그렇게 짜면 시간 초과가 뜹니다.

그래서 다른 방법 아시면 댓글 달아주심 감사하겠습니다.

또한 신경써야할 부분이 하나 더 있는데, 벽을 지나다녀서도 안되고 회전했을 때 중간에 벽이 있어도 안됩니다.

그러므로 구현이라고 하기에는 난이도가 너무 높은데 이걸 BFS로 하려고 하니 머리가 터지는줄 알았답니다.

이젠 좀 생각을 정리되었으니 차근차근 풀어보겠습니다.

 

class Point{
    int x1;
    int y1;
    int x2;
    int y2;
    int time;
    Point(int x1, int y1, int x2, int y2, int time){
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        this.time = time;
    }
}

저는 변수를 4가지로 오버라이딩 하여 받아왔습니다.

이 4가지 파라미터를 하나로 묶어서 사용해야만 문제를 이해할 수 있습니다.

time은 시간을 의미하는 파라미터입니다.

arr = board;
visit = new boolean[arr.length][arr.length][arr.length][arr.length];
visit[0][0][0][1] = true;
queue.offer(new Point(0, 0, 0, 1, 0));
bfs();
return answer;

visit배열을 생성합니다.

visit은 0,0,0,1을 true로 선언하고 queue에는 0,0,0,0,1(time)을 삽입합니다.

bfs문을 보겠습니다.

while(!queue.isEmpty()){
    Point now = queue.poll();
    if((now.x1 == arr.length - 1 && now.y1 == arr.length - 1)
    || (now.x2 == arr.length - 1 && now.y2 == arr.length - 1))
        answer = Math.min(answer, now.time);
    for(int i = 0; i < 8; i++){
        if(i >= 4){
            dfs(i, now);
            continue;
        }
        int nx1 = now.x1 + dir[i][0];
        int ny1 = now.y1 + dir[i][1];
        int nx2 = now.x2 + dir[i][0];
        int ny2 = now.y2 + dir[i][1];
        if(nx1 < 0 || ny1 < 0 || nx1 >= arr.length || ny1 >= arr.length)
            continue;
        if(nx2 < 0 || ny2 < 0 || nx2 >= arr.length || ny2 >= arr.length)
            continue;
        if(visit[nx1][ny1][nx2][ny2])
            continue;
        if(arr[nx1][ny1] == 1 || arr[nx2][ny2] == 1)
            continue;
        queue.offer(new Point(nx1, ny1, nx2, ny2, now.time + 1));
        visit[nx1][ny1][nx2][ny2] =  true;
    }
}

bfs문은 다음과 같습니다.

while문에 들어가서 queue의 nullPoint참조 값 에러를 막아주시고 queue에서 가져온 점을 now에 담아옵니다.

이 점이 (N,N)에 도달하면 정답이 되기 때문에 그 때의 time값을 answer에 담고 최솟값을 갱신합니다.

그리고 그 외의 경우에 i를 총 8번 loop하여 탐색을 진행해볼텐데요.

최초의 4번은 이동을 의미하고 이후의 4번은 회전을 의미합니다.

따라서 i가 4보다 적을 땐 다음 로직이 실행됩니다.

int nx1 = now.x1 + dir[i][0];
int ny1 = now.y1 + dir[i][1];
int nx2 = now.x2 + dir[i][0];
int ny2 = now.y2 + dir[i][1];
if(nx1 < 0 || ny1 < 0 || nx1 >= arr.length || ny1 >= arr.length)
    continue;
if(nx2 < 0 || ny2 < 0 || nx2 >= arr.length || ny2 >= arr.length)
    continue;
if(visit[nx1][ny1][nx2][ny2])
    continue;
if(arr[nx1][ny1] == 1 || arr[nx2][ny2] == 1)
    continue;
queue.offer(new Point(nx1, ny1, nx2, ny2, now.time + 1));
visit[nx1][ny1][nx2][ny2] =  true;

 여기서 받아온 nx1, ny1, nx2, ny2는 이동한 후 새로 갱신한 좌표입니다.

이 좌표가 범위를 벗어나거나 방문한 점이거나 벽인 점들은 모두 continue해주시고

그 외의 점들에 대해 queue에 삽입하고 visit을 true로 바꾸어 주시면 되겠습니다.

이동 부분은 딱히 할 게 없어서 넘어갑니다. 중요한건 이제부터입니다.

아까 전에 언급드렸듯 i가 4보다 크거나 같으면 회전이 실행될 것입니다.

if(i >= 4){
    dfs(i, now);
    continue;
}

다음과 같이 실행하여 dfs문을 살펴보겠습니다.

static void dfs(int t, Point now){
    if(now.x1 == now.x2 && t == 4) {
        if(now.y1 > now.y2){
            int temp = now.y2;
            now.y2 = now.y1;
            now.y1 = temp;
        }
        //x2, y2 이동(가로모양일 때 오른쪽에 있는)
        for (int i = 0; i < 2; i++) {
            int nx = now.x2 + move[i][0];
            int ny = now.y2 + move[i][1];
            int mx = now.x2 + dir[i][0];
            int my = now.y2 + dir[i][1];
            if(mx < 0 || my < 0 || mx >= arr.length || my >= arr.length)
                continue;
            if(arr[mx][my] == 1)
                continue;
            if (nx < 0 || ny < 0 || nx >= arr.length || ny >= arr.length)
                continue;
            if (visit[now.x1][now.y1][nx][ny])
                continue;
            if (arr[nx][ny] == 1)
                continue;
            queue.offer(new Point(now.x1, now.y1, nx, ny, now.time + 1));
            visit[now.x1][now.y1][nx][ny] = true;
        }
    }else if(now.x1 == now.x2 && t == 5){//가로모양일 때 왼쪽에 있는 x1, y1 이동
        if(now.y1 > now.y2){
            int temp = now.y2;
            now.y2 = now.y1;
            now.y1 = temp;
        }
        for (int i = 0; i < 2; i++) {
            int nx = now.x1 + move2[i][0];
            int ny = now.y1 + move2[i][1];
            int mx = now.x1 + dir[i][0];
            int my = now.y1 + dir[i][1];
            if(mx < 0 || my < 0 || mx >= arr.length || my >= arr.length)
                continue;
            if(arr[mx][my] == 1)
                continue;
            if (nx < 0 || ny < 0 || nx >= arr.length || ny >= arr.length)
                continue;
            if (visit[nx][ny][now.x2][now.y2])
                continue;
            if (arr[nx][ny] == 1)
                continue;
            queue.offer(new Point(nx, ny, now.x2, now.y2, now.time + 1));
            visit[nx][ny][now.x2][now.y2] =  true;
        }
    }else if(now.y1 == now.y2 && t == 6){ //세로 모양일 때 위에 있는 x1, y1 이동
        if(now.x1 > now.x2){
            int temp = now.x2;
            now.x2 = now.x1;
            now.x1 = temp;
        }
        for (int i = 2; i < 4; i++) {
            int nx = now.x1 + move2[i][0];
            int ny = now.y1 + move2[i][1];
            int mx = now.x1 + dir2[i][0];
            int my = now.y1 + dir2[i][1];
            if(mx < 0 || my < 0 || mx >= arr.length || my >= arr.length)
                continue;
            if(arr[mx][my] == 1)
                continue;
            if (nx < 0 || ny < 0 || nx >= arr.length || ny >= arr.length)
                continue;
            if (visit[nx][ny][now.x2][now.y2])
                continue;
            if (arr[nx][ny] == 1)
                continue;
            queue.offer(new Point(nx, ny, now.x2, now.y2, now.time + 1));
            visit[nx][ny][now.x2][now.y2] =  true;
        }
    }else if(now.y1 == now.y2 && t == 7){ //세로 모양일 때 아래에 있는 x2, y2 이동
        if(now.x1 > now.x2){
            int temp = now.x2;
            now.x2 = now.x1;
            now.x1 = temp;
        }
        for (int i = 2; i < 4; i++) {
            int nx = now.x2 + move3[i][0];
            int ny = now.y2 + move3[i][1];
            int mx = now.x2 + dir2[i][0];
            int my = now.y2 + dir2[i][1];
            if(mx < 0 || my < 0 || mx >= arr.length || my >= arr.length)
                continue;
            if(arr[mx][my] == 1)
                continue;
            if (nx < 0 || ny < 0 || nx >= arr.length || ny >= arr.length)
                continue;
            if (visit[now.x1][now.y1][nx][ny])
                continue;
            if (arr[nx][ny] == 1)
                continue;
            queue.offer(new Point(now.x1, now.y1, nx, ny, now.time + 1));
            visit[now.x1][now.y1][nx][ny] =  true;
        }
    }

dfs문은 다음과 같습니다. 이름을 dfs라 지었다고 왜 dfs냐 할 수 있겠지만 습관적으로 지은 부분이라 양해부탁드립니다.

자 여기서 받아온 t를 4, 5, 6, 7에 따라 나누어볼텐데요.

4일 때 now.x1과 now.x2가 같다면 이 도형의 모양이 가로모양일 때 가능합니다.

따라서 가로모양이면서, 오른쪽에 있는 블럭을 90도로 시계방향, 또는 반시계방향으로 움직여보겠습니다.

나올 수 있는 경우의 수는 총 2가지이기 때문에 오른쪽에 있는 블럭을 x2, y2라고 하고, 회전을 진행합니다.

만약 x1, y1이 오른쪽에 있을 수도 있는데 그럴 경우엔 y1과 y2를 서로 바꾸어 줍니다.

int nx = now.x2 + move[i][0];
int ny = now.y2 + move[i][1];
int mx = now.x2 + dir[i][0];
int my = now.y2 + dir[i][1];
if(mx < 0 || my < 0 || mx >= arr.length || my >= arr.length)
    continue;
if(arr[mx][my] == 1)
    continue;
if (nx < 0 || ny < 0 || nx >= arr.length || ny >= arr.length)
    continue;
if (visit[now.x1][now.y1][nx][ny])
    continue;
if (arr[nx][ny] == 1)
    continue;
queue.offer(new Point(now.x1, now.y1, nx, ny, now.time + 1));
visit[now.x1][now.y1][nx][ny] = true;

여기에서 nx, ny는 회전한 후 얻어낸 새로운 점을 의미하고 mx, my는 45도 움직인 부분입니다.

2차원에서는 그냥 위로 한 칸, 아래로 한 칸 움직인 것과 같기 때문에 dir배열을 통해 위 아래를 체크할 수 있습니다.

마찬가지로 nx, ny, mx, my가 범위를 벗어날 땐 continue해주시고 방문하거나 벽인 부분도 continue합니다.

이외의 점들에 대해서 queue에 담고 visit도 true로 바꾸어주면 되겠습니다.

이와 똑같이 가로 모양의 도형의 왼쪽 블록에 대해서도 위, 아래로 회전할 수 있을 것이고

세로 모양의 위의 블록에 대해서 왼,오른쪽으로 회전, 세로 모양의 아래의 블록에 대해서도 왼,오른쪽으로 회전이 가능합니다.

그렇기 때문에 총 4가지가 되어 평행 이동 4가지 + 회전 4가지가 합쳐져서 bfs문에서 총 8번의 for문을 진행했던 것입니다.

visit부분은 4차원으로 그냥 진행했는데 되어서 다른 자료구조보다 오히려 빠르지 않을까? 싶은 생각도 드네요.

그렇지만 dfs문을 너무 길게 짠 것 같아서 다른 분들 것도 참고하시는게 좋을 것 같습니다.

제 코드가 길이가 엄청 길지만 이해하시는데에는 오히려 너무 상세하게 풀어쓴 것 같아 도움이 되지 않을까 하는 0.1의 기대도 해봅니다.

다시 다른 것 공부하고 가겠습니다.

감사합니다.