프로그래머스 [2020카카오공채] 블록 이동하기 c++

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

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

 

백준의 1938번 통나무 옮기기(문제 링크)와 비슷한 느낌의 BFS 문제다.

(통나무 옮기기 풀이 링크)

 

이게 조금 더 어려운 것 같기는 하다...

좌표를 어떻게 저장할까 하다가 아래 카카오 기술 블로그에 있는 해설에서 아이디어를 얻어서 풀었다.

 

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

 

위의 해설에

(r, c, d) : (r, c) 위치에서 d 방향에 있는 칸을 한 칸 더 차지하고 있음이라고 나와있어서

로봇의 x, y좌표, 방향, 시간을 구조체로 저장해 큐에 넣어서 BFS를 진행하였다.

로봇의 나머지 한 칸은 방향 정보를 이용하여 구한다.

 

 

매번 상, 하, 좌, 우로 이동하는 경우와

로봇의 두 칸 중 한 칸에서 시계방향으로 90도 회전하는 경우 / 반시계 방향으로 90도 회전하는 경우

나머지 한 칸에서 시계방향으로 90도 회전하는 경우 /반시계 방향으로 90도 회전하는 경우 중

이동 가능한 위치(벽이 아니고 범위를 벗어나지 않는 곳)를 계속 큐에 넣어주면서 진행하면 된다.

 

 

 

로봇을 이동시킬 때, 두 칸 중 한 칸만의 좌표를 기준으로 이동시키므로

로봇의 한 칸을 (x, y)라고 하고 다른 한칸을 (xx, yy)라고 했을 때, visit 배열을 (x, y)를 기준으로 방문을 확인하고 큐에도 (x, y)좌표와 (x, y) 기준의 방향이 들어간다.

따라서 (x, y)축을 기준으로 회전할때는 (x, y)의 좌표는 변화가 없고 방향만 변화하므로 새로 큐에 넣을 때도 (x, y) 좌표 그대로와 회전된 새 방향을 넣어준다.

반대로, (xx, yy)를 축으로 (x, y)를 회전한 경우에는 (x, y)를 이동시킨 위치인 (nx, ny)를 기준으로 만들어주기 위해서 방향을 반대로 바꿔주고 큐에 넣어줄 때에도 (xx, yy)가 아닌 (nx, ny) 좌표와 (nx, ny) 기준의 방향을 넣어준다.

 

#include <vector>
#include <queue>
using namespace std;
 
int n;
bool visit[100][100][4];
 
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
 
//회전할 때 지나칠 곳
int ndx[] = { -1,1,1,-1 };
int ndy[] = { 1,1,-1,-1 };
 
struct Robot {
    int x;
    int y;
    int dir;
    int time;
    Robot(int a, int b, int d, int t) {
        x = a;
        y = b;
        dir = d;
        time = t;
    }
};
 
bool rangeCheck(int x, int y, int xx, int yy) {
    if (x < 0 || x >= n || y < 0 || y >= n) return false;
    if (xx < 0 || xx >= n || yy < 0 || yy >= n) return false;
 
    return true;
}
 
 
int solution(vector<vector<int>> board) {
 
    queue<Robot> q;
    q.push(Robot(0, 0, 0, 0));
    visit[0][0][0] = true;
 
    n = board.size();
    int destX = n - 1;
    int destY = n - 1;
 
    int cnt = 0;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        int time = q.front().time;
        q.pop();
 
        //로봇의 나머지 한칸
        int xx = x + dx[dir];
        int yy = y + dy[dir];
 
 
        //로봇의 한칸이라도 도착하면 종료
        if (x == destX && y == destY) return time;
        if (xx == destX && yy == destY) return time;
 
 
        int nx, ny, nxx, nyy;
 
        //우, 하, 좌, 상 이동
        for (int k = 0; k < 4; k++) {
            nx = x + dx[k];
            ny = y + dy[k];
            nxx = xx + dx[k];
            nyy = yy + dy[k];
            
            //이동할 곳의 범위 체크
            if (!rangeCheck(nx, ny, nxx, nyy)) continue;
            //이동할 곳의 방문 체크
            if (visit[nx][ny][dir]) continue;
            //이동할 수 있는지 체크
            if (board[nx][ny] == 1 || board[nxx][nyy] == 1) continue;
 
            visit[nx][ny][dir] = true;
            q.push(Robot(nx, ny, dir, time + 1));
 
        }
 
 
        //x,y 를 축으로 90도 회전
        for (int i = 1; i < 4; i += 2) {
            int ndir = (dir + i) % 4;
            nxx = x + dx[ndir];
            nyy = y + dy[ndir];
 
            int rx, ry; //회전하면서 지나갈 곳의 좌표
            if (i == 1) {
                //시계방향 회전인 경우
                rx = x + ndx[ndir];
                ry = y + ndy[ndir];
            }
            else {
                //반시계방향 회전인 경우
                rx = x + ndx[dir];
                ry = y + ndy[dir];
            }
            
            if (!rangeCheck(rx, ry, nxx, nyy)) continue;
            if (visit[x][y][ndir]) continue;
            if (board[nxx][nyy] == 1) continue;
            if (board[rx][ry]) continue;
 
            visit[x][y][ndir] = true;
            q.push(Robot(x, y, ndir, time + 1));
        }
        
 
        //xx, yy 를 축으로 90도 회전
        dir = (dir + 2) % 4; //xx, yy가 기준이므로 방향이 반대로 바뀐다.
        for (int i = 1; i < 4; i += 2) {
            int ndir = (dir + i) % 4;
            nx = xx + dx[ndir];
            ny = yy + dy[ndir];
 
            int rx, ry; //회전하면서 지나갈 곳의 좌표
            if (i == 1) {
                //시계방향 회전인 경우
                rx = xx + ndx[ndir];
                ry = yy + ndy[ndir];
            }
            else {
                //반시계방향 회전인 경우
                rx = xx + ndx[dir];
                ry = yy + ndy[dir];
            }
 
            if (!rangeCheck(nx, ny, rx, ry)) continue;
            if (board[nx][ny] == 1) continue;
            if (board[rx][ry] == 1) continue;
 
            ndir = (ndir + 2) % 4;
            if (visit[nx][ny][ndir]) continue;
            visit[nx][ny][ndir] = true;
            q.push(Robot(nx, ny, ndir, time + 1));
        }
        
 
 
    }
 
}