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

 

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

프로그래머스

시작 지점 -> 여러 지점 -> 도착 지점

#include <vector>
#include <queue>

using namespace std;

struct Robot {
    int x, y, dir, cost;
};

int n;
int dx[4] = {1, 0, -1, 0}; // 시계 방향(우하좌상)
int dy[4] = {0, 1, 0, -1};
int dist[100][100][4]; // 로봇 중심 지점(축) y, x, 다른 지점 방향
vector<vector<int>> Board;
queue<Robot> q;

void check(Robot now, Robot R, bool turn, int x, int y) {
    Robot R1 = {R.x, R.y, R.dir, R.cost};
    Robot R2 = {R.x + dx[R.dir], R.y + dy[R.dir], (R.dir + 2) % 4, R.cost};
    
    // 로봇 위치
    if ((R1.x < 0) || (R1.y < 0) || (R1.x >= n) || (R1.y >= n)) return;
    if ((R2.x < 0) || (R2.y < 0) || (R2.x >= n) || (R2.y >= n)) return;
    if ((Board[R1.y][R1.x]) ||(Board[R2.y][R2.x])) return;
    
    // 대각선 (bool turn 필요)
    if ((turn) && ((x < 0) || (y < 0) || (x >= n) || (y >= n))) return;
    if ((turn) && (Board[y][x])) return;

    // 로봇의 왼쪽
    if (dist[R1.y][R1.x][R1.dir] > dist[now.y][now.x][now.dir] + 1) {
        dist[R1.y][R1.x][R1.dir] = dist[now.y][now.x][now.dir] + 1;
        q.push({R1.x, R1.y, R1.dir, dist[R1.y][R1.x][R1.dir]});
    }
    
    // 로봇의 오른쪽 (반바퀴 차)
    now = {now.x + dx[now.dir], now.y + dy[now.dir], (now.dir + 2) % 4, dist[now.y + dy[now.dir]][now.x + dx[now.dir]][(now.dir + 2) % 4]};
    
    if (dist[R2.y][R2.x][R2.dir] > dist[now.y][now.x][now.dir] + 1) {
        dist[R2.y][R2.x][R2.dir] = dist[now.y][now.x][now.dir] + 1;
        q.push({R2.x, R2.y, R2.dir, dist[R2.y][R2.x][R2.dir]});
    }
}

int solution(vector<vector<int>> board) {
    n = board.size();
    Board = board;
    fill(&dist[0][0][0], &dist[n-1][n-1][4], 1e9); // 4차원 시간초과

    dist[0][0][0] = dist[0][1][2] = 0;
    
    q.push({0, 0, 0, 0}); // 중심 (0, 0), 나머지 로봇 지점은 0(오른쪽)
    q.push({1, 0, 2, 0}); // 중심 (1, 0), 나머지 로봇 지점은 2(왼쪽), x 먼저(TC 5, 11, 12)
    while(!q.empty()) {
        Robot now = q.front();
        q.pop();
        
        if (dist[now.y][now.x][now.dir] < now.cost) continue;
        if ((now.x == n-1) && (now.y == n-1)) continue;
        if ((now.x + dx[now.dir] == n-1) && (now.y + dy[now.dir] == n-1)) continue;
        
        // 모든 방향으로 로봇 형태 그대로 직진 이동
        for(int i=0; i<4; i++) check(now, {now.x+dx[i], now.y+dy[i], now.dir, now.cost}, false, 0, 0);
        
        // 회전 이동
        if (now.dir % 2 == 0) { // 가로
            check(now, {now.x, now.y, (now.dir + 1) % 4, now.cost}, true, now.x + dx[now.dir], now.y + dy[(now.dir + 1) % 4]); // 시계 방향 90도
            check(now, {now.x, now.y, (now.dir + 3) % 4, now.cost}, true, now.x + dx[now.dir], now.y + dy[(now.dir + 3) % 4]); // 시계 반대 방향 90도
        }
        else { // 세로
            check(now, {now.x, now.y, (now.dir + 1) % 4, now.cost}, true, now.x + dx[(now.dir + 1) % 4], now.y + dy[now.dir]); // 시계 방향 90도
            check(now, {now.x, now.y, (now.dir + 3) % 4, now.cost}, true, now.x + dx[(now.dir + 3) % 4], now.y + dy[now.dir]); // 시계 반대 방향 90도
        }
    }
    
    return min(dist[n-1][n-1][2], dist[n-1][n-1][3]);
}

* 시간초과

4차원 배열

#include <vector>
#include <queue>

using namespace std;

struct Robot {
    int x1, y1, x2, y2, dir, cnt;
};

int n;
int dist[100][100][100][100];
vector<vector<int>> Board;
queue<Robot> q;

void check(Robot now, Robot R, int x, int y) {
    if ((R.x1 < 0) || (R.y1 < 0) || (R.x1 >= n) || (R.y1 >= n)) return;
    if ((R.x2 < 0) || (R.y2 < 0) || (R.x2 >= n) || (R.y2 >= n)) return;
    if ((x < 0) || (y < 0) || (x >= n) || (y >= n)) return;
    
    if ((Board[y][x]) || (Board[R.y1][R.x1]) ||(Board[R.y2][R.x2])) return;
    if (dist[R.y1][R.x1][R.y2][R.x2] < dist[now.y1][now.x1][now.y2][now.x2] + 1) return;
    
    dist[R.y1][R.x1][R.y2][R.x2] = dist[now.y1][now.x1][now.y2][now.x2] + 1;
    dist[R.y2][R.x2][R.y1][R.x1] = dist[now.y2][now.x2][now.y1][now.x1] + 1;
    
    R.cnt = dist[R.y1][R.x1][R.y2][R.x2];
    q.push(R);
}

int solution(vector<vector<int>> board) {
    int d[2] = {-1, 1};
    
    n = board.size();
    Board = board;
    fill(&dist[0][0][0][0], &dist[n-1][n-1][n-1][n], 1e9); // 4차원 시간초과

    dist[0][1][0][0] = 0;
    dist[0][0][0][1] = 0;
    
    q.push({0, 0, 1, 0, 0, 0});
    while(!q.empty()) {
        Robot now = q.front();
        q.pop();
        
        if (dist[now.y1][now.x1][now.y2][now.x2] < now.cnt) continue;
        if ((now.x1 == n-1) && (now.y1 == n-1)) continue;
        if ((now.x2 == n-1) && (now.y2 == n-1)) continue;
        
        for(int i=0; i<2; i++) {
            // 모든 방향으로 로봇 형태 그대로 직진
            check(now, {now.x1+d[i], now.y1, now.x2+d[i], now.y2, now.dir, now.cnt}, 0, 0);
            check(now, {now.x1, now.y1+d[i], now.x2, now.y2+d[i], now.dir, now.cnt}, 0, 0);
            
            // 회전
            if (now.dir == 0) { // 가로 방향
                check(now, {now.x1, now.y1, now.x1, now.y1+d[i], 1, now.cnt}, now.x2, now.y1+d[i]); // 왼쪽 축
                check(now, {now.x2, now.y2, now.x2, now.y2+d[i], 1, now.cnt}, now.x1, now.y2+d[i]); // 오른쪽 축
            }
            else { // 세로 방향
                check(now, {now.x1, now.y1, now.x1+d[i], now.y1, 0, now.cnt}, now.x1+d[i], now.y2); // 위 축
                check(now, {now.x2, now.y2, now.x2+d[i], now.y2, 0, now.cnt}, now.x2+d[i], now.y1); // 아래 축
            }
        }
    }
    
    return min(dist[n-1][n-2][n-1][n-1], dist[n-2][n-1][n-1][n-1]);
}