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

프로그래머스 블록 이동하기 [2020 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/60063

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

문제 풀이

• 이 문제는 BFS로 풀었습니다. 
• {count, y, x, direction} 을 한 노드의 정보로 사용했습니다.
  • count = move 횟수
  • y = 축의 y 좌표
  • x = 축의 x 좌표
  • direction = 축을 기준으로 반대쪽이 어느 방향에 있는지 (0 - U, 1 - R, 2 - D, 3 - L)
• 다음의 코드는 로봇의 이동 및 회전 로직입니다. 

for(int d=0; d<4; ++d) {
    int ny1 = y1 + dy[d];
    int nx1 = x1 + dx[d];
    int ny2 = y2 + dy[d];
    int nx2 = x2 + dx[d];

    if(!safe(ny1, nx1) || !safe(ny2, nx2)) continue;
    if(board[ny1][nx1] || board[ny2][nx2]) continue;
	
    // 이동 가능할 때 push
    if(!visit[ny1][nx1][dir]) {
        visit[ny1][nx1][dir] = 1;
        q.push({cnt+1, ny1, nx1, dir});
    }
    if(!visit[ny2][nx2][(dir+2)%4]) {
        visit[ny2][nx2][(dir+2)%4] = 1;
        q.push({cnt+1, ny2, nx2, (dir+2)%4});
    }
	
    // 회전 가능할 때 push
    if((dir+1) % 2 == d % 2) {                
        if(!visit[y1][x1][d]) {
            visit[y1][x1][d] = 1;
            q.push({cnt+1, y1, x1, d});
        }
        if(!visit[y2][x2][(dir+2)%4]) {
            visit[y2][x2][(dir+2)%4] = 1;
            q.push({cnt+1, y2, x2, (dir+2)%4});
        }
    }
}

• 로봇을 이동하거나 회전하는게 가능할 때 로봇을 뒤집은 모양으로도 push 해 줍니다. 예를 들어 로봇이 {(0, 0), (0, 1)}에서 {(0, 1), (0, 2)}로 이동했을 때 (0, 1, 1(R -> 축 반대편이 오른쪽에 있음))와 (0, 2, 3(L -> 축 반대편이 왼쪽에 있음))을 같이 push 합니다. 
• 마찬가지로 회전도 로봇이 {(0, 0), (0, 1)}에서 {(0, 0), (1, 0)}으로 회전했다고 할 때, (0, 0, 2(D -> 축 반대편이 아래))와 (1, 0, 0(U -> 축 반대편이 위))을 같이 push합니다. 
• 위의 코드에서 (dir+2)%4 는 자신의 반대 방향 즉, R일 때 L, U일 때 D 등을 의미합니다.
• (dir+1) % 2 == d % 2 는 현재 방향과 직각인 방향을 의미합니다. R일 때 U, D / U일 때 L, R 등을 말합니다. 물론 L일 때와 D일 때도 마찬가지입니다. 
• 로봇을 규칙에 따라 이동시키면서 한 쪽이라도 (N, N) 위치에 도착하면 count를 리턴합니다

코드

#include <vector>
#include <queue>
#include <tuple>

using namespace std;

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

bool safe(int y, int x) {
    return y>=0 && x>=0 && y<N && x<N;
}

int solution(vector<vector<int>> board) {
    N = board.size();
    
    queue<tuple<int,int,int,int>> q;
    
    q.push({0, 0, 0, 1});
    visit[0][0][1] = 1;

    q.push({0, 0, 1, 3});
    visit[0][1][3] = 1;
    
    while(!q.empty()) {
        auto [cnt, y1, x1, dir] = q.front(); q.pop();

        int y2 = y1 + dy[dir];
        int x2 = x1 + dx[dir];
        
        if((y1 == N-1 && x1 == N-1) || (y2 == N-1 && x2 == N-1)) {
            return cnt;
        }
        
        for(int d=0; d<4; ++d) {
            int ny1 = y1 + dy[d];
            int nx1 = x1 + dx[d];
            int ny2 = y2 + dy[d];
            int nx2 = x2 + dx[d];
            
            if(!safe(ny1, nx1) || !safe(ny2, nx2)) continue;
            if(board[ny1][nx1] || board[ny2][nx2]) continue;
            
            if(!visit[ny1][nx1][dir]) {
                visit[ny1][nx1][dir] = 1;
                q.push({cnt+1, ny1, nx1, dir});
            }
            if(!visit[ny2][nx2][(dir+2)%4]) {
                visit[ny2][nx2][(dir+2)%4] = 1;
                q.push({cnt+1, ny2, nx2, (dir+2)%4});
            }
            
            if((dir+1) % 2 == d % 2) {                
                if(!visit[y1][x1][d]) {
                    visit[y1][x1][d] = 1;
                    q.push({cnt+1, y1, x1, d});
                }
                if(!visit[y2][x2][(dir+2)%4]) {
                    visit[y2][x2][(dir+2)%4] = 1;
                    q.push({cnt+1, y2, x2, (dir+2)%4});
                }
            }
        }
    }
    
    return 0;
}

실행 결과