[프로그래머스 lv3] 블록 이동하기 풀이

 

해당 문제는 2020 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

 

 

해설

(1, 1) 에서 (N, N)까지 도달하는 최단 경로를 구하는 문제로, bfs를 이용하여 해결할 수 있다.

 

1) bfs를 이용하여 최단 시간(거리)을 구할 때, 특정 좌표까지의 거리를 기록하는 dist 배열을 만들어야 한다. 그런데, 이 문제에서는 로봇이 두 칸에 걸쳐 이동하고 심지어 방향까지 가지고 있다. 따라서, 특정 좌표를 방문했는지 그리고 해당 좌표까지의 거리가 얼마인지 기록하는 배열은 3차원이 되어야 한다. dist[x][y][d]는 (x, y)에 d 방향으로 도달했을 때 (d = 0이면 오른쪽으로, d = 1이면 아래쪽으로) 해당 좌표까지 걸린 시간(거리)을 의미한다.

 

2) 로봇은 가장 처음 (1, 1) 에 오른쪽 방향으로 놓여있다. 따라서, dist[1][1][0]은 0이고 q에 (1, 1, 0)을 삽입할 수 있다. 이후, 큐에서 방문한 좌표들의 정보를 하나씩 꺼내 해당 좌표에서 이동할 수 있는 새로운 좌표를 탐색하고 해당 좌표를 큐에 넣으면 된다.

 

3) (x, y, d) 에서 이동할 수 있는 좌표는,

- 상하좌우로 이동한 좌표이다. 상하좌우로 이동한 좌표가 범위를 벗어나지 않고 모두 board값이 0이면서 아직 방문하지 않았을 때 해당 좌표까지의 거리를 기록하고 큐에 넣는다.

- 90도 방향으로 회전한 좌표이다. 로봇의 두 좌표를 각각 회전축으로 하여 이동할 때, 회전축의 대각선 방향 좌표, 새로운 두 좌표가 조건을 만족한다면 해당 좌표까지의 거리를 기록하고 큐에 넣는다.

- 90도 회전 후, 방향이 0이었던 로봇의 방향은 1이 되고, 방향이 1이었던 로봇의 방향은 0이 된다.

 

4) 큐에서 좌표를 꺼냈을 떄, 로봇의 두 좌표 중 하나라도 (N, N) 위에 있으면 dist[x][y][d]를 리턴한다.

 

해결방법을 생각해내는 건 어렵지 않았는데, 회전했을 때의 경우를 모두 따져보는게 까다로웠다.^^;

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int rdx0[4] = {-1, 1, -1, 1};
int rdy0[4] = {1, 1, 0, 0};
int rnx0[4] = {-1, 0, -1, 0};
int rny0[4] = {0, 0, 1, 1};

int rdx1[4] = {1, 1, 0, 0};
int rdy1[4] = {-1, 1, 1, -1};
int rnx1[4] = {0, 0, 1, 1};
int rny1[4] = {-1, 0, 0, -1};

int x, y, d, N;
int brd[105][105];
int dist[105][105][2];

void setArr(const vector<vector<int>>& board) {
    
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++)
            brd[i][j] = board[i-1][j-1];
    }
    
    for (int i=0; i<105; i++) {
        for (int j=0; j<105; j++) {
            for (int k=0; k<2; k++)
                dist[i][j][k] = -1;
        }
    }
}

bool check(int a, int b, int dir) {
    
    if (a == N && b == N) return true;
    if (a+dx[dir] == N && b+dy[dir] == N) return true;
    return false;
}

bool OOB(int a, int b) {
    return a <= 0 || a > N || b <= 0 || b > N;
}

int bfs(const vector<vector<int>>& board) {
    
    queue<iii> q;
    q.push({1, 1, 0});
    dist[1][1][0] = 0;

    while (!q.empty()) {
        
        tie(x, y, d) = q.front();
        if (check(x, y, d)) return dist[x][y][d];
        q.pop();
        
        //상하좌우 이동
        for (int i=0; i<4; i++) {
            int nx1 = x+dx[i];
            int ny1 = y+dy[i];
            int nx2 = x+dx[d]+dx[i];
            int ny2 = y+dy[d]+dy[i];
            if (OOB(nx1, ny1) || OOB(nx2, ny2)) continue;
            if (brd[nx1][ny1] || brd[nx2][ny2]) continue;
            if (dist[nx1][ny1][d] != -1) continue;
            q.push({nx1, ny1, d});
            dist[nx1][ny1][d] = dist[x][y][d]+1;
        }
        
        //회전
        if (d == 0) {
            for (int i=0; i<4; i++) {
                int chx = x+rdx0[i];
                int chy = y+rdy0[i];
                int nx1 = x+rnx0[i];
                int ny1 = y+rny0[i];
                int nx2 = nx1+dx[1];
                int ny2 = ny1+dy[1];
                if (OOB(chx, chy) || OOB(nx1, ny1) || OOB(nx2, ny2)) continue;
                if (brd[chx][chy] || brd[nx1][ny1] || brd[nx2][ny2]) continue;
                if (dist[nx1][ny1][1] != -1) continue;
                q.push({nx1, ny1, 1});
                dist[nx1][ny1][1] = dist[x][y][d]+1;
            }
        }
        else {
            for (int i=0; i<4; i++) {
                int chx = x+rdx1[i];
                int chy = y+rdy1[i];
                int nx1 = x+rnx1[i];
                int ny1 = y+rny1[i];
                int nx2 = nx1+dx[0];
                int ny2 = ny1+dy[0];
                if (OOB(chx, chy) || OOB(nx1, ny1) || OOB(nx2, ny2)) continue;
                if (brd[chx][chy] || brd[nx1][ny1] || brd[nx2][ny2]) continue;
                if (dist[nx1][ny1][0] != -1) continue;
                q.push({nx1, ny1, 0});
                dist[nx1][ny1][0] = dist[x][y][d]+1;
            }
        }
        
    }
    
    return -1;
}

int solution(vector<vector<int>> board) {
    
    N = (int)board.size();
    setArr(board);
    return bfs(board);
}