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

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

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

 

풀이

이 문제는 BFS 알고리즘을 이용해서 해결 가능한 문제입니다.

큐에 <(r1, c1,), (r2, c2), time>을 모두 넣어주었습니다.

처음엔 <(0,0), (0,1),0>을 넣고 큐가 텅 빌 때까지 아래의 과정을 반복합니다.

1. 우선 큐의 맨앞 좌표 값을 pop합니다. pop할 때 마다 목적지에 도착한지 여부를 확인합니다. (도착한 경우 time을 반환하고 끝)
2. 현 위치에서 상하좌우 이동방향으로 이동가능한지 여부를 확인해 이동가능한 경우 큐에 push해줍니다.
3. 이 때 방문여부는 visit[0][n][n]을 이용하는데 3차원 배열을 이용하는 이유는 로봇이 가로 또는 세로 두가지가 모두 가능하기 때문에 따로 방문을 확인하기 때문입니다.(방문 여부는 r, c가 작은쪽을 기준으로 확인합니다.)
4. 그런 뒤 회전 가능 여부를 확인해 가능한 경우 동일하게 큐에 push합니다. (회전 가능여부는 위의 그림처럼 8가지 경우를 확인합니다.)

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int visit[2][101][101];     //0:가로, 1: 세로
queue<pair<pair<pair<int, int>, pair<int, int>>, int>> q; //(r1, c1),(r2, c2), time

int solution(vector<vector<int>> board) {
    int answer = 0;
    int R[4] = {1, -1, 0, 0};
    int C[4] = {0, 0, 1, -1};
    int n = board.size();
    
    q.push(make_pair(make_pair(make_pair(0,0), make_pair(0,1)),0));
    visit[0][0][0] = 1;
    
    while(!q.empty()){
        int r1 = q.front().first.first.first;
        int c1 = q.front().first.first.second;
        int r2 = q.front().first.second.first;
        int c2 = q.front().first.second.second;
        int time = q.front().second;
        q.pop();
        
        if((r1 == n-1 && c1 == n-1) || (r2 == n-1 && c2 == n-1)){
            return time;  
        }
        
        int check_dir;
        //가로
        if(r1 == r2)
            check_dir = 0;
        //세로
        else
            check_dir = 1;
        //상하좌우 이동 확인
        for(int i=0; i<4; i++){
            int next_r1 = r1+R[i];
            int next_c1 = c1+C[i];
            int next_r2 = r2+R[i];
            int next_c2 = c2+C[i];
            int check_r, check_c;
            if(next_r1 <0 || next_r1 >= n || next_c1 <0 || next_c1 >= n)
                continue;
            if(next_r2 <0 || next_r2 >= n || next_c2 <0 || next_c2 >= n)
                continue;
            if(board[next_r1][next_c1] ==1 || board[next_r2][next_c2] == 1)
                continue;
            
            //방문여부 확인
            if(next_r1 == next_r2){
                check_c = min(next_c1, next_c2);
                check_r = next_r1;
            }
            if(next_c1 == next_c2){
                check_r = min(next_r1, next_r2);
                check_c = next_c1;
            }
            if(visit[check_dir][check_r][check_c] == 1)
                continue;
            
            
            q.push(make_pair(make_pair(make_pair(next_r1,next_c1), make_pair(next_r2,next_c2)),time+1));
            visit[check_dir][check_r][check_c] = 1;
        }
        
        //회전 확인
        //가로
        if(check_dir == 0){
            int next_c1 = c2;
            int next_r1 = r1-1;
            //(r1, c1)이동
            if(next_r1 >=0 && !board[next_r1][c1] && !board[next_r1][c2] && !visit[1][next_r1][next_c1]){
                q.push(make_pair(make_pair(make_pair(next_r1,next_c1), make_pair(r2,c2)),time+1));
                visit[1][next_r1][next_c1]=1;
            }
            next_r1 = r1+1;
            if(next_r1 < n && !board[next_r1][c1] && !board[next_r1][c2] && !visit[1][r1][next_c1]){
                q.push(make_pair(make_pair(make_pair(next_r1,next_c1), make_pair(r2,c2)),time+1));
                visit[1][r1][next_c1]=1;
            }
            //(r2, c2) 이동
            int next_c2 = c1;
            int next_r2 = r2-1;
            if(next_r2 >=0 && !board[next_r2][c1] && !board[next_r2][c2] && !visit[1][next_r2][next_c2]){
                q.push(make_pair(make_pair(make_pair(r1,c1), make_pair(next_r2,next_c2)),time+1));
                visit[1][next_r2][next_c2]=1;
            }
            next_r2 = r2+1;
            if(next_r2 <n && !board[next_r2][c1] && !board[next_r2][c2] && !visit[1][r2][next_c2]){
                q.push(make_pair(make_pair(make_pair(r1,c1), make_pair(next_r2,next_c2)),time+1));
                visit[1][r2][next_c2]=1;
            }
        }
        
        //세로
        else{
            int next_c1 = c1-1;
            int next_r1 = r2;
            //(r1, c1)이동
            if(next_c1 >=0 && !board[r1][next_c1] && !board[r2][next_c1] && !visit[0][next_r1][next_c1]){
                q.push(make_pair(make_pair(make_pair(next_r1,next_c1), make_pair(r2,c2)),time+1));
                visit[0][next_r1][next_c1]=1;
            }
            next_c1 = c1+1;
            if(next_c1 < n && !board[r1][next_c1] && !board[r2][next_c1] && !visit[0][next_r1][c1]){
                q.push(make_pair(make_pair(make_pair(next_r1,next_c1), make_pair(r2,c2)),time+1));
                visit[0][next_r1][c1]=1;
            }
            
            //(r2, c2) 이동
            int next_c2 = c2-1;
            int next_r2 = r1;
            if(next_c2 >=0 && !board[r1][next_c2] && !board[r2][next_c2] && !visit[0][next_r2][next_c2]){
                q.push(make_pair(make_pair(make_pair(r1,c1), make_pair(next_r2,next_c2)),time+1));
                visit[0][next_r2][next_c2]=1;
            }
            next_c2 = c2+1;
            if(next_c2 < n && !board[r1][next_c2] && !board[r2][next_c2] && !visit[0][next_r2][c2]){
                q.push(make_pair(make_pair(make_pair(r1,c1), make_pair(next_r2,next_c2)),time+1));
                visit[0][next_r2][c2]=1;
            }
        }
    }
    
    
    return answer;
}