[백준 30055][구현] 우주비행사 정민

출제 배경

ZOAC 2023에서 출제한.. 뭐랄까 대회에서 나오면 안되는 문제를 내버렸다. 삼성 코테 A~B번에 나올 법한 문제로, 실수하기 좋은 구현 문제이다. 그래도 입력 범위가 나름 널널하게 주어져서 최적화를 많이 신경쓰지 않아도 충분히 풀 수 있다고 생각한다.

 

 

문제 설명

문제 링크

먼저 2차원 격자 모양으로 이뤄진 2개의 차원이 있다. 두 차원의 크기는 다를 수 있다.

 

또한 두 차원을 이어주는 차원 이동 게이트가 존재한다. 게이트 또한 2차원 격자 모양으로 이뤄졌으며, 반대편 차원에, 게이트 상에서 정민이가 위치한 자리로 이동한다.

 

정민이는 상하좌우로 한 번 움직이는데에 1초가 걸리고, 차원 이동을 하는데에는 3초가 걸린다.

 

이제 블랙홀에 대해 알아보자. 블랙홀은 위와 같이 확산된다. 정민이는 블랙홀과 겹쳐선 안된다. 차원 이동 게이트 또한 블랙홀에 덮힐 수 있으며, 만약 정민이가 차원 이동을 시도할 때, 차원 이동 소모 시간인 3초 후에 반대편 차원의 차원 이동 게이트에서 정민이가 소환되는 자리에 블랙홀이 있다면 차원 이동을 수행할 수 없다. 블랙홀은 정민이가 이동한 후에 확산된다.

 

이러한 상황 속에서 차원 1의 좌측  상단 (0,0)에서 차원 2의 우측 하단 (N-1, N-1)까지 도달하는데에 필요한 최소 시간을 구하는 문제이다. (참 더럽다)

 

블랙홀은 시간에 따라 정해진 곳으로 확산되므로, 각 위치에 블랙홀이 몇 초에 생성되는지 계산해둔다. 예를 들어 배열의 (3,4)의 값이 5라면 5초인 시점에 (3,4) 위치에 블랙홀이 생성되는 것이다. 이제 BFS를 이용하여 정민이가 이동하는 경우와, 정민이가 차원이동 하는 경우로 5가지로 나누어 탐색한다. 이 때, 이미 이동한 곳을 다시 이동하는 경우는 없다. 블랙홀은 점차 확산하기만 하기에 제자리를 왔다갔다 하는 경우는 없는 것이다.

 

다만, 돌아가는 경우는 있다. 블랙홀로 가로막혀있어, 위 또는 좌측으로 돌아갈 수는 있다. 또 차원 이동 게이트를 여러 번 탈 수도 있다. 보통 이 경우에서 반례가 생기는 것 같다.

 

 

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

#define MAX_N 200
#define MAX_M 200

int k,n1,m1,n2,m2,gate_x,gate_y,gate_x1,gate_y1,gate_x2,gate_y2;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int blackhole1[MAX_N][MAX_M];
int blackhole2[MAX_N][MAX_M];

void add_blackhole(int blackhole_num, int x, int y){
    int cnt = 0;
    while(cnt < n1*m1+n2*m2){
        //차원에 따른 저장
        if(blackhole_num == 1){
            if(blackhole1[x][y] < cnt) return;
            blackhole1[x][y] = cnt;
        }
        else{
            if(blackhole2[x][y] < cnt) return;
            blackhole2[x][y] = cnt;
        }
        // x가 홀수 일 때
        if(x%2){
            if(y==0) x = (x+1)%(blackhole_num == 1 ? n1 : n2);
            else --y;
        }
        // x가 짝수일 때
        else{
            if(y==(blackhole_num == 1 ? m1-1 : m2-1)) ++x;
            else ++y;
        }
        ++cnt;
    }
}

inline bool now_position_is_gate(int dimention_num, int x, int y){
    return
    (dimention_num == 1 && gate_x1 <= x && x <= gate_x1+gate_x && gate_y1 <= y && y <= gate_y1+gate_y) ||
    (dimention_num == 2 && gate_x2 <= x && x <= gate_x2+gate_x && gate_y2 <= y && y <= gate_y2+gate_y);
}

inline pair<int,int> position_if_can_teleport(int curr_dimention_num, int x, int y, int curr_t){
    int rx = curr_dimention_num == 1 ? x - gate_x1 : x - gate_x2;
    int ry = curr_dimention_num == 1 ? y - gate_y1 : y - gate_y2;
    auto next_position = make_pair((curr_dimention_num == 1 ? gate_x2 + rx : gate_x1 + rx),
                                    (curr_dimention_num == 1 ? gate_y2 + ry : gate_y1 + ry)
        );
    if(curr_dimention_num == 1 ? blackhole2[next_position.first][next_position.second] <= curr_t+3 
        : blackhole1[next_position.first][next_position.second] <= curr_t+3) 
            return make_pair(-1,-1);
    return next_position;
}

inline pair<int,int> position_if_can_move(int dimention_num, int x, int y, int direction, int curr_t){
    int nx = x + dir[direction][0], ny = y + dir[direction][1];
    if(nx<0 || ny<0 || 
    (dimention_num == 1 && (nx>=n1 || ny>=m1 || blackhole1[nx][ny] <= curr_t + 1)) || 
    (dimention_num == 2 && (nx>=n2 || ny>=m2 || blackhole2[nx][ny] <= curr_t + 1))
    ) return make_pair(-1, -1);
    return make_pair(nx, ny);
}

void solve(){
    int ans = 2e8;
    if(blackhole1[0][0] == 0){
        cout<<"hing..."; return;
    }
    queue<pair<pair<int, int>,pair<int, int> > > q;
    vector<vector<int> > dis1(n1, vector<int>(m1, 2e8));
    vector<vector<int> > dis2(n2, vector<int>(m2, 2e8));
    q.push(make_pair(make_pair(1, 0), make_pair(0, 0)));
    dis1[0][0] = 0;
    while(!q.empty()){
        int d = q.front().first.first, t = q.front().first.second,
            x = q.front().second.first, y = q.front().second.second;
        q.pop();

        for(int i=0; i<4; i++){
            auto p = position_if_can_move(d, x, y, i, t);
            if(p.first != -1){
                int nx = p.first, ny = p.second;
                if(d==1 && dis1[nx][ny] > t+1){
                    dis1[nx][ny] = t+1;
                    q.push(make_pair(make_pair(1, t+1),make_pair(nx,ny)));
                }
                else if(d==2 && dis2[nx][ny] > t+1){
                    dis2[nx][ny] = t+1;
                    q.push(make_pair(make_pair(2, t+1),make_pair(nx,ny)));
                }
            }
        }
        if(now_position_is_gate(d,x,y)){
            auto p = position_if_can_teleport(d, x, y, t);
            if(p.first != -1){
                int nx = p.first, ny = p.second;
                if(d==1 && dis2[nx][ny] > t+3){
                    dis2[nx][ny] = t+3;
                    q.push(make_pair(make_pair(2, t+3),make_pair(nx,ny)));
                }
                else if(d==2 && dis1[nx][ny] > t+3){
                    dis1[nx][ny] = t+3;
                    q.push(make_pair(make_pair(1, t+3),make_pair(nx,ny)));
                }
            }
        }
    }

    ans = dis2[n2-1][m2-1];

    if(ans == 2e8) cout<<"hing...";
    else cout<<ans;
}

int main(){
    cin>>k>>n1>>m1>>n2>>m2>>gate_x>>gate_y>>gate_x1>>gate_y1>>gate_x2>>gate_y2;
    --gate_x;
    --gate_y;
    // 블랙홀 초기화
    for(int i=0; i<n1; i++){
        for(int j=0; j<m1; j++){
            blackhole1[i][j] = 2e8;
        }
    }
    for(int i=0; i<n2; i++){
        for(int j=0; j<m2; j++){
            blackhole2[i][j] = 2e8;
        }
    }
    for(int i=0; i<k; i++){
        int d,dx,dy; scanf("%d %d %d", &d, &dx, &dy);
        add_blackhole(d, dx, dy);
    }
    solve();
}