2020 카카오 신입사원 코딩테스트 - 블록 이동하기

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

코딩테스트 연습 - 블록 이동하기 | 프로그래머스

 

오늘은 2020 카카오 코딩테스트 풀이 다섯번째 시간 입니다.

이번 문제는 아주 전형적인 BFS + 구현 문제 입니다.

 

BFS의 기초는 https://yomyom0824.tistory.com/3?category=1081200 여기에서 익히고 오시면 됩니다.

 

여기서 배울 부분은 단순 동서남북 이동에 대한 것보다는 '회전에 대한 것' 입니다.

 

 

 

 

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
 
using namespace std;
 
struct pos{
    int y[2], x[2];
    int dir[2];
};
int n;
int dy[] = {0,1,0,-1};  // -> 0 / 아래 1 / <- 2 / 위 3
int dx[] = {1,0,-1,0};
bool chk[101][101][4];
 
bool range(int y1, int x1, int y2, int x2, int dir1, int dir2, vector<vector<int>> &mp){
    return !(y1 < 0 || y1 >= n || x1 < 0 || x1 >= n || y2 < 0 || y2 >= n || x2 < 0 || x2 >= n || mp[y1][x1] || mp[y2][x2]);
}
 
int solution(vector<vector<int>> mp) {
    n = mp.size();
    queue<pos> q;
    // -> 0 / 아래 1 / <- 2 / 위 3
    chk[0][0][0] = chk[0][1][2] = true;
    q.push({0,0,0,1,0,2});
    int timer = 0;
    while(!q.empty()){
        int l = q.size();
        while(l--){
            pos f = q.front();
            q.pop();
 
            if((f.y[0] == n - 1 && f.x[0] == n - 1) || (f.y[1] == n - 1 && f.x[1] == n - 1)) return timer;
 
            for(int dir = 0; dir < 4; dir++){
                int ny1 = f.y[0] + dy[dir], nx1 = f.x[0] + dx[dir];
                int ny2 = f.y[1] + dy[dir], nx2 = f.x[1] + dx[dir];
                int dir1 = f.dir[0], dir2 = f.dir[1];
                
                if(!range(ny1, nx1, ny2, nx2, dir1, dir2, mp) || chk[ny1][nx1][dir1] || chk[ny2][nx2][dir2]) continue;
                chk[ny1][nx1][dir1] = chk[ny2][nx2][dir2] = true;
                q.push({ny1, ny2, nx1, nx2, dir1, dir2});
            }
 
            for(int i = -1; i <= 1; i++){
                if(i == 0) continue;
                for(int j = 0; j < 2; j++){
                    int y = f.y[j], x = f.x[j];
 
                    int dir = (f.dir[j] + i + 4) % 4;
                    int prev_dir = (dir - i + 4) % 4;
                    int oppo_dir = (dir + 2) % 4;
 
                    int ny2 = y + dy[dir], nx2 = x + dx[dir];
                    int ny3 = y + dy[dir] + dy[prev_dir], nx3 = x + dx[dir] + dx[prev_dir];
                    
                    if(!range(ny2, nx2, ny3, nx3, dir, oppo_dir, mp) || chk[y][x][dir] || chk[ny2][nx2][oppo_dir]) continue;
                    chk[y][x][dir] = chk[ny2][nx2][oppo_dir] = true;
                    q.push({y, ny2, x, nx2, dir, oppo_dir});
                }
            }
        }
        timer += 1;
    }
}