[프로그래머스][2020 KAKAO BLIND][C++] 블록 이동하기

문제

프로그래머스 2020 KAKAO BLIND RECRUITMENT - 블록 이동하기 (Level 3)

코딩테스트 연습 - 블록 이동하기

 

---

문제 풀이

접근 방식

이 문제는 2020 카카오 블라인드 채용 1차 코딩테스트 7번 문제로, 정답률이 1.7%인 쉽지 않은 문제였다.

 

구하고자 하는 것은 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간이다.

이 문제는 최소 시간을 구하는 기존의 BFS + DP 문제와 푸는 방식은 비슷했지만,

로봇이 점 두 개로 이루어져 있어서 구현하기가 복잡하였다.

 

이 문제를 기존의 방식처럼 풀기 위해 로봇을 점 두 개가 아닌 점 1개와 방향(가로/세로)으로 생각해주었다.

그래서 Robot 구조체에 이동 횟수(move), 방향(dir : 가로 방향은 -1, 세로 방향은 1), 위치(x, y)를 저장해주었다.

즉, 가로 방향인 경우에는 왼쪽에 있는 점의 위치와 가로 방향을 Robot에 저장하였고,

세로 방향인 경우에는 위쪽에 있는 점의 위치와 세로 방향을 Robot에 저장해주었다.

그리고 3차원 벡터 MIN을 이용하여 각 방향별 최소 이동 횟수를 저장할 수 있도록 구현하였다.

 

처음에는 큐에 (0, 0) 위치에 가로 방향으로 있는 로봇을 넣어주고 BFS 탐색을 수행하였다.

로봇이 이동할 수 있는 경우는 방향별로 각 8가지이다.

각 방향별로 이동할 수 있는지 판단하는 조건문은 모든 경우를 꼼꼼하게 체크하기 위해 하드 코딩으로 작성해주었다.

이동할 수 있는지를 확인한 후, (현재 이동 횟수 + 1)의 값이 그 위치와 방향의 MIN 값보다 작은 경우에만

MIN값을 바꿔주고 다음 위치의 로봇을 큐에 push 하며 (N, N) 위치에 도달하는 최소 시간을 구해주었다.

 

---

풀이 코드 - C++

#include <vector>
#include <queue>
using namespace std;

struct Robot {
    int move;
    int dir;
    int x;
    int y;
};

int solution(vector<vector<int>> board) {
    int len = board.size();
    int dir1[4][2] = {{0, 2},{1,0},{0,-1},{-1,0}};
    int dir2[4][2] = {{2,0},{0,-1},{-1,0},{0,1}};    
    int MIN[100][100][2];
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len; j++) {
            for(int k = 0; k < 2; k++) {
                MIN[i][j][k] = 987654321;
            }
        }
    }
    MIN[0][0][0] = 0;
    
    queue<Robot> q;
    q.push({0,-1,0,0});    
    while(!q.empty()){
        Robot now = q.front(); q.pop();
        if(now.dir == -1){  // 가로 방향
            if(now.x == len - 1 && now.y == len - 2)
                return now.move;
            for(int i = 0; i < 4; i++) {
                int nx = now.x + dir1[i][0];
                int ny = now.y + dir1[i][1];
                if(nx < 0 || ny < 0 || nx >= len || ny >= len || board[nx][ny] == 1) continue;
                switch(i) {
                case 0:
                    if(MIN[nx][ny - 1][0] > now.move + 1){
                        MIN[nx][ny - 1][0] = now.move + 1;
                        q.push({now.move + 1, now.dir, nx, ny - 1});
                    }
                    break;
                case 1:
                    if(board[nx][ny + 1] == 0){
                        if(MIN[now.x][now.y][1] > now.move + 1){
                            MIN[now.x][now.y][1] = now.move + 1;
                            q.push({now.move + 1, -now.dir, now.x, now.y});
                        }
                        if(MIN[now.x][now.y + 1][1] > now.move + 1){
                            MIN[now.x][now.y + 1][1] = now.move + 1;
                            q.push({now.move + 1, -now.dir, now.x, now.y + 1});
                        }
                        if(MIN[nx][ny][0] > now.move + 1){
                            MIN[nx][ny][0] = now.move + 1;
                            q.push({now.move + 1, now.dir, nx, ny});
                        }
                    }
                    break;
                case 2:
                    if(MIN[nx][ny][0] > now.move + 1){
                        MIN[nx][ny][0] = now.move + 1;                        
                        q.push({now.move + 1, now.dir, nx, ny});
                    }
                    break;
                case 3:
                    if(board[nx][ny + 1] == 0){
                        if(MIN[nx][ny][1] > now.move + 1){
                            MIN[nx][ny][1] = now.move + 1;
                            q.push({now.move + 1, -now.dir, nx, ny});
                        }
                        if(MIN[nx][ny + 1][1] > now.move + 1){
                            MIN[nx][ny + 1][1] = now.move + 1;
                            q.push({now.move + 1, -now.dir, nx, ny + 1});
                        }                        
                        if(MIN[nx][ny][0] > now.move + 1){
                            MIN[nx][ny][0] = now.move + 1;
                            q.push({now.move + 1, now.dir, nx, ny});
                        }
                    }
                    break;
                }
            }
        } else {    // 세로 방향
            if(now.x == len - 2 && now.y == len - 1)
                return now.move;
            for(int i = 0; i < 4; i++) {
                int nx = now.x + dir2[i][0];
                int ny = now.y + dir2[i][1];
                if(nx < 0 || ny < 0 || nx >= len || ny >= len || board[nx][ny] == 1) continue;
                switch(i) {
                case 0:
                    if(MIN[nx - 1][ny][1] > now.move + 1){
                        MIN[nx - 1][ny][1] = now.move + 1;
                        q.push({now.move + 1, now.dir, nx - 1, ny});
                    }
                    break;
                case 1:
                    if(board[nx + 1][ny] == 0){
                        if(MIN[nx][ny][0] > now.move + 1){
                            MIN[nx][ny][0] = now.move + 1;
                            q.push({now.move + 1, -now.dir, nx, ny});
                        }
                        if(MIN[nx + 1][ny][0] > now.move + 1){
                            MIN[nx + 1][ny][0] = now.move + 1;
                            q.push({now.move + 1, -now.dir, nx + 1, ny});
                        }                        
                        if(MIN[nx][ny][1] > now.move + 1){
                            MIN[nx][ny][1] = now.move + 1;
                            q.push({now.move + 1, now.dir, nx, ny});
                        }
                    }
                    break;
                case 2:
                    if(MIN[nx][ny][1] > now.move + 1){
                        MIN[nx][ny][1] = now.move + 1;
                        q.push({now.move + 1, now.dir, nx, ny});
                    }
                    break;
                case 3:                        
                    if(board[nx + 1][ny] == 0){
                        if(MIN[now.x][now.y][0] > now.move + 1){
                            MIN[now.x][now.y][0] = now.move + 1;
                            q.push({now.move + 1, -now.dir, now.x, now.y});
                        }
                        if(MIN[now.x + 1][now.y][0] > now.move + 1){
                            MIN[now.x + 1][now.y][0] = now.move + 1;
                            q.push({now.move + 1, -now.dir, now.x + 1, now.y});
                        }
                        if(MIN[nx][ny][1] > now.move + 1){
                            MIN[nx][ny][1] = now.move + 1;
                            q.push({now.move + 1, now.dir, nx, ny});
                        }
                    }
                    break;
                }
            }
        }
    }
}

실행 결과

실행 결과 : 100.0