2020 KAKAO BLIND RECRUITMENT - 블록 이동하기

2020 KAKAO BLIND RECRUITMENT - 블록 이동하기

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

접근

처음에 바보같이 DFS로 했다가 실패했습니다. 버릇처럼 BFS해야될 부분에서도 DFS하는데, 이런 부분을 고쳐야 될것 같습니다.

로봇의 현재상태가 회전을 감안해야 하고, 2자리를 차지한다라는 것을 제외하면 일반적인 BFS를 사용하는 최단거리 문제입니다.

구현

의식의 흐름대로 코드짜다보면 전체적으로 감당못할 사이즈나 예외가 발생할 수 있기 때문에 설계부터 꼼꼼해야 하는 문제입니다.

일반적인 BFS에서 필요한 정보는

1. 방문할 곳의 위치
2. 방문했다는 표시(visit)
3. 최단거리
4. (optional) 최단경로

입니다.

이 문제에서 1,2,3,4를 관통하는 어려운 부분은 지금 로봇의 위치표현 입니다. 일반적으로는 1x1크기이기 떄문에 (r,c)형태로 표현 가능하지만, 이 로봇의 경우 2칸을 차지하기 때문에 두점의 위치(r1,c1,r2,c2)로 표현해야 하며 두 점의 위치가 바뀌어도 같은 위치로 인식해야 합니다.

또한 회전이 가능하기 때문에 BFS에서 탐색해야 될 방향은 다음과 같은 총 8가지 방향입니다.

1. 위
2. 아래
3. 왼쪽
4. 오른쪽
5. r1을 축으로 시계방향
6. r2를 축으로 시계방향
7. r1을 축으로 반시계방향
8. r2를 축으로 반시계방향

따라서 이 문제의 핵심은 다음으로 요약 할 수 있습니다.

- 로봇의 현재 위치 표현

- 회전 구현

로봇의 현재 위치 표현은 그냥 두점의 위치를 모두 고려하였습니다. 다만 두점의 위치만 서로 swap된 경우는 같은 위치로 따로 고려했습니다.

그래서 visit을 4차원(...)배열로 구현했습니다. visit[r1][c1][r2][c2] 의 형태로 구현하였는데 공간 복잡도를 전혀 고려하지 않은것 같기도 합니다.

회전 구현은 따로 함수를 만들었습니다.

bool rotating(int r1,int r2,int c1,int c2,int std,int clock) 

형태의 함수로 두 점의 위치를 받고, std(축)의 정보와 clock(시계방향인지 아닌지)를 받아서

회전이 가능하다면 전역변수에 축이 아닌 블록이 이동해야할 위치를 저장하고 true를 return하며

회전이 불가능하면 false를 return합니다.

후기

해설을 보니 로봇의 현재위치 표현을 저 처럼 두 점의 위치가 아닌
(r,c,d) 형태로 표현했습니다 ( r,c에 한 블록, r,c에서 d방향으로 한 블록)

저렇게 하면 공간복잡도를 훨씬 줄일수 있고 속도도 훨씬 빠를 것 같습니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>
#include <string.h>
#include <queue>
#include <utility>

using namespace std;


void dfs(int r1,int r2,int c1,int c2,int t,int d);
bool rotating(int r1,int r2,int c1,int c2,int std,int clock);
int board[103][103];
int visit[103][103][103][103];
int n,t1,t2;

int solution(vector<vector<int>> b) {
    int answer = 0;
    
    queue<pair<int,int>> q;
    queue<int> d;
    n = int(b.size());
    memset(board,1,sizeof(board));
    memset(visit,0,sizeof(visit));
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n; j++){
            board[i+1][j+1] = b[i][j];
        }
    }
    
    //for(int i = 0 ; i < 6 ; i++) dfs(1, 1, 1, 2, 0, i);
    
    q.push(pair<int, int>(1,1));
    q.push(pair<int, int>(1,2));
    d.push(0);
    visit[1][1][1][2] = 1;
    int r1,r2,c1,c2,td;
    while (!q.empty()) {
        r1 = q.front().first;
        c1 = q.front().second;
        q.pop();
        r2 = q.front().first;
        c2 = q.front().second;
        q.pop();
        td = d.front();
        d.pop();
        
        if ((r1 == n && c1 == n) || (r2==n && c2==n)){
            answer = td;
            break;
        }
        else{
            if (board[r1][c1+1] == 0 && board[r2][c2+1] == 0){ //right
                if(visit[r1][c1+1][r2][c2+1] == 0 && visit[r2][c2+1][r1][c1+1] == 0){
                    visit[r1][c1+1][r2][c2+1] = 1;
                    q.push(pair<int,int>(r1,c1+1));
                    q.push(pair<int,int>(r2,c2+1));
                    d.push(td+1);
                }
            }
            if (board[r1][c1-1] == 0 && board[r2][c2-1] == 0){ //left
                if(visit[r1][c1-1][r2][c2-1] == 0 && visit[r2][c2-1][r1][c1-1] == 0){
                    visit[r1][c1+1][r2][c2+1] = 1;
                    q.push(pair<int,int>(r1,c1-1));
                    q.push(pair<int,int>(r2,c2-1));
                    d.push(td+1);
                }
            }
            if (board[r1-1][c1] == 0 && board[r2-1][c2] == 0){ //up
                if(visit[r1-1][c1][r2-1][c2] == 0 && visit[r2-1][c2][r1-1][c1] == 0){
                    visit[r1-1][c1][r2-1][c2] = 1;
                    q.push(pair<int,int>(r1-1,c1));
                    q.push(pair<int,int>(r2-1,c2));
                    d.push(td+1);
                }
            }
            if (board[r1+1][c1] == 0 && board[r2+1][c2] == 0){ //down
                if(visit[r1+1][c1][r2+1][c2] == 0 && visit[r2+1][c2][r1+1][c1] == 0){
                    visit[r1-1][c1][r2-1][c2] = 1;
                    q.push(pair<int,int>(r1+1,c1));
                    q.push(pair<int,int>(r2+1,c2));
                    d.push(td+1);
                }
            }
            if (rotating(r1, r2, c1, c2, 0, 1)) { //r1 clock
                if(visit[r1][c1][t1][t2] == 0 && visit[t1][t2][r1][c1] == 0){
                    visit[r1][c1][t1][t2] = 1;
                    q.push(pair<int,int>(r1,c1));
                    q.push(pair<int,int>(t1,t2));
                    d.push(td+1);
                }
            }
            if (rotating(r1, r2, c1, c2, 1, 1)) { //r2 clock
                if(visit[r2][c2][t1][t2] == 0 && visit[t1][t2][r2][c2] == 0){
                    visit[r2][c2][t1][t2] = 1;
                    q.push(pair<int,int>(t1,t2));
                    q.push(pair<int,int>(r2,c2));
                    d.push(td+1);
                }
            }
            if (rotating(r1, r2, c1, c2, 0, 0)) { //r1 rclock
                if(visit[r1][c1][t1][t2] == 0 && visit[t1][t2][r1][c1] == 0){
                    visit[r1][c1][t1][t2] = 1;
                    q.push(pair<int,int>(r1,c1));
                    q.push(pair<int,int>(t1,t2));
                    d.push(td+1);
                }
            }
            if (rotating(r1, r2, c1, c2, 1, 0)) { //r2 rclock
                if(visit[r2][c2][t1][t2] == 0 && visit[t1][t2][r2][c2] == 0){
                    visit[r2][c2][t1][t2] = 1;
                    q.push(pair<int,int>(t1,t2));
                    q.push(pair<int,int>(r2,c2));
                    d.push(td+1);
                }
            }
        }
        
    }
    
    
    return answer;
}
bool rotating(int r1,int r2,int c1,int c2,int std,int clock){
    if (r1 == r2) { // horizon
        if (std == 0) { //r1 std
            if (c1<c2) { //left std
                if (clock) { //clock
                    if (board[r1+1][c1] == 0 && board[r1+1][c1+1] == 0) {
                        t1 = r1+1;
                        t2 = c1;
                        return true;
                    }
                }else{ //rclock
                    if (board[r1-1][c1] == 0 && board[r1-1][c1+1] == 0) {
                        t1 = r1-1;
                        t2 = c1;
                        return true;
                    }
                }
            }else{ //right std
                if (clock) { //clock
                    if (board[r1-1][c1] == 0 && board[r1-1][c1-1] == 0) {
                        t1 = r1-1;
                        t2 = c1;
                        return true;
                    }
                }else{ //rclock
                    if (board[r1+1][c1] == 0 && board[r1+1][c1-1] == 0) {
                        t1 = r1+1;
                        t2 = c1;
                        return true;
                    }
                }
            }
        }else{//r2 std
            if (c1<c2) { //right std
                if (clock) { //clock
                    if (board[r2-1][c2] == 0 && board[r2-1][c2-1] == 0) {
                        t1 = r2-1;
                        t2 = c2;
                        return true;
                    }
                }else{ //rclock
                    if (board[r2+1][c2] == 0 && board[r2+1][c2-1] == 0) {
                        t1 = r2+1;
                        t2 = c2;
                        return true;
                    }
                }
            }else{ //left std
                if (clock) { //clock
                    if (board[r2+1][c2] == 0 && board[r2+1][c2+1] == 0) {
                        t1 = r2+1;
                        t2 = c2;
                        return true;
                    }
                }else{ //rclock
                    if (board[r2-1][c2] == 0 && board[r2-1][c2+1] == 0) {
                        t1 = r2-1;
                        t2 = c2;
                        return true;
                    }
                }
            }
        }
        
        
    }else{ // vertical
        if(std == 0){ //r1 std
            if(r1 < r2){ //up std
                if (clock) {//clock
                    if (board[r1][c1-1] == 0 && board[r1+1][c1-1] == 0) {
                        t1 = r1;
                        t2 = c1-1;
                        return true;
                    }
                }else{//rclock
                    if (board[r1][c1+1] == 0 && board[r1+1][c1+1] == 0) {
                        t1 = r1;
                        t2 = c1+1;
                        return true;
                    }
                }
            }else{ //down std
                if (clock) {//clock
                    if (board[r1][c1+1] == 0 && board[r1-1][c1+1] == 0) {
                        t1 = r1;
                        t2 = c1+1;
                        return true;
                    }
                }else{//rclock
                    if (board[r1][c1-1] == 0 && board[r1-1][c1-1] == 0) {
                        t1 = r1;
                        t2 = c1-1;
                        return true;
                    }
                }
            }
            
            
        }else{ //r2 std
            if(r1 > r2){ //up std
                if (clock) {//clock
                    if (board[r2][c2-1] == 0 && board[r2+1][c2-1] == 0) {
                        t1 = r2;
                        t2 = c2-1;
                        return true;
                    }
                }else{//rclock
                    if (board[r2][c2+1] == 0 && board[r2+1][c2+1] == 0) {
                        t1 = r2;
                        t2 = c2+1;
                        return true;
                    }
                }
            }else{ //down std
                if (clock) {//clock
                    if (board[r2][c2+1] == 0 && board[r2-1][c2+1] == 0) {
                        t1 = r2;
                        t2 = c2+1;
                        return true;
                    }
                }else{//rclock
                    if (board[r2][c2-1] == 0 && board[r2-1][c2-1] == 0) {
                        t1 = r2;
                        t2 = c2-1;
                        return true;
                    }
                }
            }
        }
    
    }
    return false;
}