[프로그래머스 Lv3] : 블록 이동하기

문제 링크

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

프로그래머스

로봇이 지도의 가장 끝점인 (N, N)까지 이동하는 데 필요한 최소 시간을 리턴해주자.

 

풀이

 무지의 로봇은 2칸을 차지하는 로봇이다.

상,하,좌,우로 이동하거나 90도 회전이 가능하다.

문제를 제대로 안 읽고 놓여져있는 방향으로만 이동이 가능한 줄 알고 문제를 풀어서 시간을 낭비했다..

 

탐색 방법은 BFS를 이용하고, 방문체크가 중요하다.

로봇이 두 칸을 차지하기 때문에 1차원 배열로 방문을 체크하게 되면, 세로로 접근했을 때와 가로로 접근했을 때를 구분하지 못한다.

visited배열을 4차원으로 만들어서 로봇이 차지하고 있는 두 칸의 좌표를 pos1, pos2라고 했을 때,

visited[pos1_y][pos1_x][pos2_y][pos2_x] 이렇게 표시를 할 수 있도록 했다.

 

상관은 없지만

좌우로 놓여있을 땐 항상 왼쪽에 있는 칸을 pos1,

상하로 놓여있을 땐 항상 위쪽에 있는 칸을 pos1 이라고 정했다.

 

이제 로봇의 이동을 통제해주자.

위와 같이 로봇이 가로로 놓여져 있다고 하자.

범위를 벗어나지 않는 선에서, 상하좌우로의 이동과 4방향 회전을 모두 고려해야한다.

 

먼저 상하좌우로의 이동을 살펴보면

상 : 위로 이동하기 위해선 ①번 두 칸에 벽이 없어야 한다.

하 : 아래로 이동하기 위해선 ②번 두 칸에 벽이 없어야 한다.

우 : 오른쪽으로 이동하기 위해선 ③번에 벽이 없어야 한다.

좌 : 왼쪽으로 이동하기 위해선 ④번에 벽이 없어야 한다.

 

다음으로 회전을 살펴보면

① : ①번 방향으로 회전하기 위해선 ①번 두 칸에 모두 벽이 없어야 한다.

② : ②번 방향으로 회전하기 위해선 ②번 두 칸에 모두 벽이 없어야 한다.

 

로봇이 세로로 놓여있을 때도 같은 맥락으로 상황을 고려해주면 된다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
bool visited[105][105][105][105];
int ans = 987654321;
 
bool is_ok(pair<int,int> pos, int n, vector<vector<int>>& board){
    if(pos.first < 0 || pos.first >= n || pos.second < 0 || pos.second >= n || board[pos.first][pos.second])
        return false;
    return true;
}
 
int solution(vector<vector<int>> board) {
    int answer = 0;
    int n = board.size();
    //Priority_queue pq;
    queue<pair<pair<int,pair<int,int>>, pair<int,int>>> q;
    q.push({{0,{0,0}},{0,1}});
    
    while(!q.empty()){
        int T = q.front().first.first;
        pair<int,int> pos1 = q.front().first.second;
        pair<int,int> pos2 = q.front().second;
        q.pop();
        
        if(visited[pos1.first][pos1.second][pos2.first][pos2.second])
            continue;
        visited[pos1.first][pos1.second][pos2.first][pos2.second] = true;
        
        if(pos2.first == n - 1 && pos2.second == n - 1){
            answer = T;
            break;
        }
        
        if(pos1.first == pos2.first){ //현재 가로방향
            pair<int,int> next = {pos2.first, pos2.second + 1}; //오른쪽으로 이동
            if(is_ok(next, n, board) && !visited[pos2.first][pos2.second][next.first][next.second])
                q.push({{T + 1, pos2},next});
            
            next = {pos1.first, pos1.second - 1}; // 왼쪽으로
            if(is_ok(next, n, board) && !visited[next.first][next.second][pos1.first][pos1.second])
                q.push({{T + 1, next},pos1});
 
            next = {pos1.first + 1, pos1.second}; // 왼쪽 회전
            
            if(is_ok(next, n, board) && is_ok({pos2.first + 1, pos2.second}, n, board)
              && !visited[next.first][next.second][pos2.first + 1][pos2.second])
                q.push({{T + 1, next}, {pos2.first + 1, pos2.second}});
            
            if(is_ok(next, n, board) && !visited[pos1.first][pos1.second][next.first][next.second]
              && !board[pos2.first + 1][pos2.second])
                q.push({{T + 1, pos1},next});
            
            next = {pos2.first + 1, pos2.second}; // 오른쪽 회전
            if(is_ok(next, n, board) && !visited[pos2.first][pos2.second][next.first][next.second]
              && !board[pos1.first + 1][pos1.second])
                q.push({{T + 1, pos2},next});
 
            next = {pos1.first - 1, pos1.second};
            if(is_ok(next, n, board) && is_ok({pos2.first - 1, pos2.second}, n, board)
              && !visited[next.first][next.second][pos2.first - 1][pos2.second])
                q.push({{T + 1, next}, {pos2.first - 1, pos2.second}});
            
            if(is_ok(next, n, board) && !visited[next.first][next.second][pos1.first][pos1.second]
              && !board[pos2.first - 1][pos2.second])
                q.push({{T + 1, next},pos1});
            
            next = {pos2.first - 1, pos2.second};
            if(is_ok(next, n, board) && !visited[next.first][next.second][pos2.first][pos2.second]
              && !board[pos1.first - 1][pos1.second])
                q.push({{T + 1, next},pos2});
        }
        else if(pos1.second == pos2.second){ //세로 방향
            pair<int,int> next = {pos2.first + 1, pos2.second}; //아래로
            if(is_ok(next, n, board) && !visited[pos2.first][pos2.second][next.first][next.second])
                q.push({{T + 1, pos2},next});
            
            next = {pos1.first - 1, pos1.second}; //위로
            if(is_ok(next, n, board) && !visited[next.first][next.second][pos1.first][pos1.second])
                q.push({{T + 1, next},pos1});
 
            next = {pos1.first, pos1.second + 1};
            if(is_ok(next, n, board) && is_ok({pos2.first, pos2.second + 1}, n, board)
              && !visited[next.first][next.second][pos2.first][pos2.second + 1])
                q.push({{T + 1, next}, {pos2.first, pos2.second + 1}});
            
            if(is_ok(next, n , board) && !visited[pos1.first][pos1.second][next.first][next.second]
               && !board[pos2.first][pos2.second + 1])
                q.push({{T + 1, pos1}, next});
            
            next = {pos2.first, pos2.second + 1};
            if(is_ok(next, n , board) && !visited[pos2.first][pos2.second][next.first][next.second] 
               && !board[pos1.first][pos1.second + 1])
                q.push({{T + 1, pos2}, next});
 
            next = {pos1.first, pos1.second - 1};
            if(is_ok(next,n, board) && is_ok({pos2.first, pos2.second - 1}, n, board)
              && !visited[next.first][next.second][pos2.first][pos2.second - 1])
                q.push({{T + 1, next}, {pos2.first, pos2.second - 1}});
            
            if(is_ok(next, n , board) && !visited[next.first][next.second][pos1.first][pos1.second]
               && !board[pos2.first][pos2.second - 1])
                q.push({{T + 1, next},pos1});
 
            next = {pos2.first, pos2.second - 1};
            if(is_ok(next, n , board) && !visited[next.first][next.second][pos2.first][pos2.second]
               && !board[pos1.first][pos1.second - 1])
                q.push({{T + 1, next},pos2});
        }
    }
    return answer;
}

처음에 이동 방향을 잘못 안 채 코드를 작성한 후 나중에 코드를 추가해서 코드가 엉망이 됐다.