블록 이동하기 (C++) 2020 KAKAO BLIND RECRUITMENT

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

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

 

0. 문제 개요

가로 혹은 세로로 두 칸을 차지하는 로봇이 있다.

로봇은 상하좌우로 이동하거나 한 칸을 축으로 회전할 수 있다.

로봇이 (n,n)에 위치하기까지 최소 시간을 구하라.

 

 

 

 

1. 문제 해결 아이디어

 

  1-1.  도착 점까지 최소 시간이므로 BFS를 이용한다.

 

  1-2. 두 칸을 차지한다는 것을 고려해야 한다. -> 로봇이 가로 모양일 때는 왼쪽 칸을, 로봇이 세로 모양일 때는 위쪽 칸을 기준으로 (x,y)를 설정한다.  -> visited[로봇 모양][x][y] : 3차원 배열로 위치 관리가 가능하다.

 

  1-3. 로봇의 회전을 구현해야 한다. 연필로 끄적여보고 다음과 같은 규칙을 발견했다.

아래에서 py,px는 로봇 모양에 따른 기준점을 가리킨다.

(로봇이 가로 모양일 때는 왼쪽 칸을, 로봇이 세로 모양일 때는 위쪽 칸)

 

• 가로 모양일 때 회전
  (1) 왼쪽을 축으로
    1. py,px -> py-1,px 위쪽으로 회전     // 대각선 : py-1,px+1
    2.  py,px -> py,px 아래쪽으로 회전    // 대각선 : py+1,px+1
  
  (2) 오른쪽을 축으로
    1. py,px -> py-1,px+1 위로 회전        // 대각선 : py-1,px
    2. py,px -> py, px+1 아래로 회전       // 대각선 : py+1,px
  
  
• 세로 모양일 때 회전
  (1) 위쪽을 축으로
    1. py,px -> py,px-1 왼쪽으로 회전      // 대각선 : py+1,px-1
    2.  py,px -> py,px 오른쪽으로 회전     // 대각선 : py+1,px+1
  
  (2) 아래쪽을 축으로
    1. py,px -> py+1,px-1 왼쪽으로 회전   // 대각선 : py,px-1
    2. py,px -> py+1, px 오른쪽으로 회전  //대각선 : py,px+1

 

 

2. 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
//stat(가로 OR 세로), cnt(BFS 이동 횟수) , y,x
queue<pair< pair<int, int>, pair<int, int>>> q;    
int visited[2][101][101];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int n;
vector<vector<int>> map;
int isPossible(int px, int py, int stat) {
 
    //기준이 되는 부분말고 로봇의 나머지 부분의 위치도 고려
    if(stat==0){
        if (px < 0 || px >= n - 1 || py < 0 || py > n - 1 || map[py][px] == 1 || map[py][px+1]==1)
        return -1;
    }
    
    else{    //로봇이 가로인지 세로인지에 따라 이동 가능 조건이 다르다.
        if (px < 0 || px > n - 1 || py < 0 || py >= n - 1 || map[py][px] == 1 || map[py+1][px]==1)
        return -1;
    }
    return 1;
}
 
int bfs() {
    int px, py, nx, ny, stat, cnt;
    q.push({ {0,0},{0,0} });
    visited[0][0][0] = 1;
 
    while (!q.empty()) {
        int flag = 0;
        px = q.front().second.second;
        py = q.front().second.first;
        
        stat = q.front().first.first;
        cnt = q.front().first.second;
        q.pop();
        
        if (stat == 0) {
            if (px + 1 == n - 1 && py == n - 1) {
                //도착
                flag = 1;
            }
        }
        if (stat == 1) {
            if (px == n - 1 && py + 1 == n - 1) {
                //도착
                flag = 1;
            }
        }
        if (flag == 1) {
            return cnt;
        }
 
        //이동
        for (int i = 0;i < 4;i++) {
            nx = px + dx[i];
            ny = py + dy[i];
            
            if (isPossible(nx, ny, stat) == 1 && visited[stat][ny][nx] == 0) {
                if (stat == 0) {
                    if (map[ny][nx + 1] == 0) {
                        visited[stat][ny][nx] = 1;
                        q.push({ {stat,cnt + 1},{ny,nx} });
                    }
                }
                else {
                    if (map[ny + 1][nx] == 0) {
                        visited[stat][ny][nx] = 1;
                        q.push({ {stat,cnt + 1},{ny,nx} });
                    }
                }
            }
        }
        //회전
        if (stat == 0) {    //현재 가로방향
            //4가지 case.
            nx = px, ny = py - 1;
            //회전 후 로봇이 놓일 위치가 비어있어야함
            if (isPossible(nx, ny, 1-stat) == 1 && visited[1 - stat][ny][nx] == 0) {
                //회전 시 대각선 위치가 비어 있어야함
                if (map[py - 1][px + 1] == 0  ) {
                    visited[1 - stat][ny][nx] = 1;
                    q.push({ {1 - stat,cnt + 1},{ny,nx} });
                }
            }
            nx = px, ny = py;
            if (isPossible(nx, ny, 1-stat) == 1 && visited[1 - stat][ny][nx] == 0) {
                if (map[py + 1][px + 1] == 0) {
                    visited[1 - stat][ny][nx] = 1;
                    q.push({ {1 - stat,cnt + 1},{ny,nx} });
                }
            }
            nx = px + 1, ny = py - 1;
            if (isPossible(nx, ny, 1-stat) == 1 && visited[1 - stat][ny][nx] == 0) {
                if (map[py - 1][px] == 0) {
                    visited[1 - stat][ny][nx] = 1;
                    q.push({ {1 - stat,cnt + 1},{ny,nx} });
                }
            }
            nx = px + 1, ny = py;
            if (isPossible(nx, ny, 1-stat) == 1 && visited[1 - stat][ny][nx] == 0) {
                if (map[py + 1][px] == 0) {
                    visited[1 - stat][ny][nx] = 1;
                    q.push({ {1 - stat,cnt + 1},{ny,nx} });
                }
            }
 
        }
        else {    //현재 세로방향
            nx = px - 1, ny = py;
            if ( isPossible(nx, ny, 1-stat) == 1 && visited[1 - stat][ny][nx] == 0) {
                if (map[py + 1][px - 1] == 0) {
                    visited[1 - stat][ny][nx] = 1;
                    q.push({ {1 - stat,cnt + 1},{ny,nx} });
                }
            }
            nx = px, ny = py;
            if (isPossible(nx, ny, 1-stat) == 1 && visited[1 - stat][ny][nx] == 0) {
                if (map[py + 1][px + 1] == 0) {
                    visited[1 - stat][ny][nx] = 1;
                    q.push({ {1 - stat,cnt + 1},{ny,nx} });
                }
            }
            nx = px - 1, ny = py + 1;
            if ( isPossible(nx, ny, 1-stat) == 1 && visited[1 - stat][ny][nx] == 0) {
                if (map[py][px - 1] == 0) {
                    visited[1 - stat][ny][nx] = 1;
                    q.push({ {1 - stat,cnt + 1},{ny,nx} });
                }
            }
            nx = px, ny = py + 1;
            if (isPossible(nx, ny, 1-stat) == 1 && visited[1 - stat][ny][nx] == 0) {
                if (map[py][px + 1] == 0) {
                    visited[1 - stat][ny][nx] = 1;
                    q.push({ {1 - stat,cnt + 1},{ny,nx} });
                }
            }
 
        }
 
 
    }
 
    return cnt;
}
 
int solution(vector<vector<int>> board) {
    int answer = 0;
    //전역 변수로 복사
    map = board;
    n = board.size();
    answer = bfs();
 
    return answer;
}

 

 

3. 나가며... (삽질했던 내용)

  3-1. 상하좌우 이동시 기준점만 고려해줬었다.. 로봇의 나머지 부분이 이동가능한지 또한 고려해야 한다.

  3-2.  로봇이 놓인 모양에 따라 이동가능 체크 방식이 달라야한다.