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

문제 링크

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

 

 

 

풀이

여러 블로그를 참고하고 카카오 공식 해설도 보고 문제를 풀었다.

맥락은 구조체로 (row, col, direction, time)으로 최소시간을 구하는 것이니 Queue를 사용하여 BFS를 구현하는 것이었다.

 

// 변수명

중심 좌표(r, c) == 방문을 결정하는 좌표

(rr, cc) == 나머지 좌표

size == board size

isLying == 가로면 true, 세로면 false (로봇이 누워있는지 여부)

Queue<Robot> == Robot 구조체를 담는 큐

visit[100][100][2] == 방문 확인 배열, 문제에서 board 범위가 5이상 100이하이므로 100 크기를 미리 선언, [2]는 가로인지, 세로인지 여부

 

// 함수

1. rangeCheck(r, c, rr, cc, size) : 범위 확인, board size에 맞는지

2. check(r, c, rr, cc, board) : 현재 로봇의 위치가 벽인지 아닌지

3. isArrive(r, c, rr, cc, size) : 도착한 것은 아닌지

 

// Process

1. Queue에 root를 넣어준다.

2. pop()

3. 함수(1, 2, 3) + 방문 여부 확인을 한다.

4. 방문을 true한다.

5. 누워있는 여부에 따라 나머지 좌표도 설정

6.1. 이동 4가지(우, 하, 상, 좌) --- 미리 row, col에 해당한 1차원 배열로 Look up table을 만들어 활용 --- 조건없이 push

6.2. 회전 4가지(눕혀있을 경우 + 범위 체크, 벽 여부 체크) --- (r, c)축 2가지, (rr, cc) 2가지 --- 범위와 벽인지 여부만 체크

{2 ~ 6 반복}

 

// 주의

- 방문 여부 확인을 하는 배열의 일관성을 위해서 회전했을 경우, 중심이 바뀌는지 여부를 확인해야 한다.

- 13, 14번이 계속 틀리길래 여러 실험해본 경우, 방문 여부확인 배열을 false로 초기화 해주기(당연히 default가 false인줄, 지역 변수라 그런가...?)

 

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

// 구조체: 로봇 위치 row, col, isLying, time
// (r, c)의 시계 방향 90도, (rr, cc)의 시계 방향 90도 --- 2가지
// (r, c)의 반시계 방향 90도, (rr, cc)의 반시계 방향 90도 --- 2가지
// 상, 하, 좌, 우 이동 --- 4가지

typedef struct Robot{
    int row, col;   // 중심 좌표
    bool isLying;   // 누워있는지
    int time;       // 최소 시간
    Robot(int _row, int _col, bool _isLying, int _time){
        // 생성자
        row = _row;
        col = _col;
        isLying = _isLying;
        time = _time;
    }
}Robot;

bool rangeCheck(int r, int c, int rr, int cc, int size){
    if(r < 0 || r >= size) return false;
    if(c < 0 || c >= size) return false;
    if(rr < 0 || rr >= size) return false;
    if(cc < 0 || cc >= size) return false;
    return true;
}

bool check(int r, int c, int rr, int cc, vector<vector<int>> board){
    if(board[r][c] == 1) return false;
    if(board[rr][cc] == 1) return false;
    return true;
}

bool isArrive(int r, int c, int rr, int cc, int size){
    if(r == size-1 && c == size-1) return true;
    if(rr == size-1 && cc == size-1) return true;
    return false;
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    const int size = board.size();
    bool visit[100][100][2] = {false, };
    int moveR[] = {0, 1, 0, -1};     // 우, 하, 좌, 상
    int moveC[] = {1, 0, -1, 0};     // 우, 하, 좌, 상
    queue<Robot> rq;                // BFS
    
    // 초기 Robot
    rq.push(Robot(0, 0, true, 0));
    
    while(!rq.empty()){
        // pop()
        int r = rq.front().row;
        int c = rq.front().col;
        bool isL = rq.front().isLying;
        int time = rq.front().time;
        rq.pop();
        
        // 나머지 좌표
        int rr = isL ? r : r+1;
        int cc = isL ? c+1 : c;
        answer = time-1;
        if(!rangeCheck(r, c, rr, cc, size)) continue;        // 보드 범위인지
        if(!check(r, c, rr, cc, board)) continue;           // 벽인지
        if(visit[r][c][(int)isL]) continue;      // 방문했는지
        if(isArrive(r, c, rr, cc, size)) return time;     // 도착했는지
        visit[r][c][(int)isL] = true;              // 방문 체크
        
        // printf("(%d, %d) + (%d, %d) + time(%d) + isLying(%d)\n", r, c, rr, cc, time, isL);
        // 이동
        for(int i=0; i<4; i++){
            int row = r + moveR[i];
            int col = c + moveC[i];
            rq.push(Robot(row, col, isL, time+1));    // BFS
        }
        
        // 회전
        bool isLying = !isL;     // 눕혀있는건 서있게, 서있는건 눕혀있게
        if(isL){
            // 눕혀있다
            if(rangeCheck(r+1, c, rr+1, cc, size) && check(r+1, c, rr+1, cc, board)){
                // 아래
                rq.push(Robot(r, c, isLying, time+1));
                rq.push(Robot(rr, cc, isLying, time+1));
            }
            if(rangeCheck(r-1, c, rr-1, cc, size) && check(r-1, c, rr-1, cc, board)){
                // 위(중심이 바뀜)
                rq.push(Robot(r-1, c, isLying, time+1));
                rq.push(Robot(rr-1, cc, isLying, time+1));
            }
        }
        else{
            // 서 있다
            if(rangeCheck(r, c+1, rr, cc+1, size) && check(r, c+1, rr, cc+1, board)){
                // 오른쪽
                rq.push(Robot(r, c, isLying, time+1));
                rq.push(Robot(rr, cc, isLying, time+1));
            }
            if(rangeCheck(r, c-1, rr, cc-1, size) && check(r, c-1, rr, cc-1, board)){
                // 왼쪽(중심이 바뀜)
                rq.push(Robot(r, c-1, isLying, time+1));
                rq.push(Robot(rr, cc-1, isLying, time+1));
            }
        }
    }
    
    return answer;
}