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

2020 카카오 블라인드 채용 코딩 테스트 문제입니다.

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

문제 확인

 

3차원 bfs 문제입니다.

 

풀이

 

visited 배열을 visited[100][100][2], 3차원으로 둡니다. 앞 2차원은 위치이며 마지막 [2]에 해당하는 차원은 로봇이 가로, 세로 상태로 방문함을 의미합니다.

 

로봇의 좌표를 (ax, ay), (bx, by)로 두고 항상 a에 해당하는 좌표가 b 좌표보다 위, 왼쪽에 위치하도록 유지합니다.

 

(a) (b)

혹은

(a)

(b)

형태로 유지함으로써 로봇 이동, 회전 시 조건 검사를 줄일 수 있습니다.

 

이동의 경우 a, b 좌표 모두 이동하여 배열의 내부, 벽이 아닌 경우 큐에 push 합니다.

회전의 경우 이동의 특성을 이용하여 회전을 시킬 수 있습니다.

• 가로의 경우 왼쪽, 오른쪽으로 이동하는 경우 회전하지 않고 둡니다.
• 가로의 경우 위, 아래쪽으로 이동이 가능한 경우 해당 방향으로 회전이 가능하다는 의미를 포함합니다. a, b 좌표 모두 이동을 할 수 있으므로 움직이는 방향에 공백 2칸이 있다는 의미입니다.
• 세로의 경우 반대로 왼쪽, 오른쪽을 이동하는 경우 회전을 합니다.

 

회전 또한 a, b 위치 조건을 만족하게끔 회전을 합니다.

 

a, b 위치를 일정하게 유지함으로써 오른쪽 이동시 by, 왼쪽 이동시 ay, 상, 하 이동도 마찬가지로 배열 범위를 벗어나가는지 하나의 좌표로 검사가 가능합니다.

목적지에 도착하는 좌표는 항상 b 좌표이므로 이를 이용하여 종료 조건을 설정합니다.

 

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;
 
typedef struct node{
    int ax, ay, bx, by, stat;
    node(int ax, int ay, int bx, int by, int s) :ax(ax), ay(ay), bx(bx), by(by), stat(s) {};
}node;
 
int solution(vector<vector<int>> board) {
 
    int n = board.size();
 
    bool visited[100][100][2] = { 0 };//0: - 가로, 1: | 세로
    queue<node> que;
    
    que.emplace( 0, 0, 0, 1, 0 );
 
    int depth = 0;
    while (!que.empty()) {
        int cur_size = que.size();//최단경로를 찾는 문제이므로 같은 depth를 한번에 처리
        while (cur_size--) {
            node cur = que.front();
            que.pop();
            if (cur.bx == n - 1 && cur.by == n - 1) return depth;//목적지 도달
            if (visited[cur.ax][cur.ay][cur.stat]) continue;
            visited[cur.ax][cur.ay][cur.stat] = 1;//방문 체크
 
            node next = { cur.ax, cur.ay + 1, cur.bx, cur.by + 1, cur.stat }; //오
            if (next.by < n && !visited[next.ax][next.ay][next.stat] && !board[next.ax][next.ay] && !board[next.bx][next.by]) {
                que.push(next);
                if (cur.stat) {//회전
                    que.emplace( cur.ax, cur.ay, cur.ax, cur.ay + 1, 0 );
                    que.emplace( cur.bx, cur.by, cur.bx, cur.by + 1, 0 );
                }
            }
 
            next = { cur.ax, cur.ay - 1, cur.bx, cur.by - 1, cur.stat }; //왼
            if (0 <= next.ay && !visited[next.ax][next.ay][next.stat] && !board[next.ax][next.ay] && !board[next.bx][next.by]) {
                que.push(next);
                if (cur.stat) {
                    que.emplace( cur.ax, cur.ay - 1, cur.ax, cur.ay, 0 );
                    que.emplace( cur.bx, cur.by - 1, cur.bx, cur.by, 0 );
                }
            }
 
            next = { cur.ax + 1, cur.ay, cur.bx + 1, cur.by, cur.stat }; //하
            if (next.bx < n && !visited[next.ax][next.ay][next.stat] && !board[next.ax][next.ay] && !board[next.bx][next.by]) {
                que.push(next);
                if (!cur.stat) {
                    que.emplace( cur.ax, cur.ay, cur.ax + 1, cur.ay, 1 );
                    que.emplace( cur.bx, cur.by, cur.bx + 1, cur.by, 1 );
                }
            }
 
            next = { cur.ax - 1, cur.ay, cur.bx - 1, cur.by, cur.stat }; //상
            if (0 <= next.ax && !visited[next.ax][next.ay][next.stat] && !board[next.ax][next.ay] && !board[next.bx][next.by]) {
                que.push(next);
                if (!cur.stat) {
                    que.emplace( cur.ax - 1, cur.ay, cur.ax, cur.ay, 1 );
                    que.emplace( cur.bx - 1, cur.by, cur.bx, cur.by, 1 );
                }
            }
        }
 
        depth++;
    }
 
    
}

정확성 테스트

테스트 1 〉	통과 (0.02ms, 3.96MB)
테스트 2 〉	통과 (0.02ms, 3.96MB)
테스트 3 〉	통과 (0.02ms, 3.77MB)
테스트 4 〉	통과 (0.03ms, 3.95MB)
테스트 5 〉	통과 (0.03ms, 3.95MB)
테스트 6 〉	통과 (0.03ms, 3.94MB)
테스트 7 〉	통과 (0.04ms, 3.94MB)
테스트 8 〉	통과 (0.05ms, 3.94MB)
테스트 9 〉	통과 (0.06ms, 3.95MB)
테스트 10 〉	통과 (0.05ms, 3.89MB)
테스트 11 〉	통과 (0.04ms, 3.94MB)
테스트 12 〉	통과 (0.04ms, 3.97MB)
테스트 13 〉	통과 (0.26ms, 4.05MB)
테스트 14 〉	통과 (0.33ms, 3.97MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0