BOJ 30055 - 우주비행사 정민 링크
(2024.04.13 기준 P5)

문제

$N_1 \times M_1$ 크기의 차원 $1$에 정민이가 $(0, 0)$ 위치에 있고, $N_2 \times M_2$ 크기의 차원 $2$에 우주선이 $(N_2 - 1, M_2 - 1)$ 위치에 있다.

블랙홀은 처음에 $K$개가 있다. 이 블랙홀은 우주의 기류에 따라 매초 새로운 블랙홀을 생성한다.

기류는 행 번호가 짝수일 때는 열 번호가 증가하는 방향으로 흐르고, 홀수일 때는 감소하는 방향으로 흐른다. 더 이상 이동할 수 없으면 행 번호가 증가하는 방향으로 한 번 흐른다. $(N-1, 0)$에 도달하면 $(0,0)$으로 이동하여 같은 방식으로 순환한다.

차원 이동 게이트는 각 차원에 $A \times B$의 같은 크기로 하나씩 존재한다. 위치는 다를 수 있다. 게이트를 이용해 다른 차원에 $3$초 후 도착할 수 있다. 이때, 동일한 게이트 내부 좌표로 이동한다. 또한 차원 이동하는 $3$초 동안은 블랙홀에 휩쓸리지 않는다.

정민이가 우주선에 도착하는 최단 시간 출력

알고리즘

구현 많은 BFS 문제

풀이

문제 지문 그대로 구현하면 된다.

일단 각 칸마다 블랙홀이 도착하는 시간을 구하자.

그리고 정민이의 위치인 $(1, 0, 0)$ (차원, 행, 열)부터 BFS를 진행하면 된다.
이때, 주의해야 할 점은 두 가지가 있다.
1. 항상 어느 칸으로 이동할 땐, 그 칸에 도착하는 시간이 블랙홀이 도착하는 시간보다 일찍이어야 한다.
2. 게이트를 이용할 때, 차원 $2$에서 차원 $1$로도 이용할 수 있다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int inf = 1e9;
const pii dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

    int K, N1, M1, N2, M2, A, B, R1, C1, R2, C2;
    cin >> K >> N1 >> M1 >> N2 >> M2 >> A >> B >> R1 >> C1 >> R2 >> C2;

    // 블랙홀이 도달하는 거리 구하기
    int dist1_[N1][M1]; fill(&dist1_[0][0], &dist1_[N1 - 1][M1], inf); // 차원 1
    int dist2_[N2][M2]; fill(&dist2_[0][0], &dist2_[N2 - 1][M2], inf); // 차원 2
    queue<tiii> q;
    for (int d, r, c; K; K--){
        cin >> d >> r >> c;
        if (d == 1){
            dist1_[r][c] = 0;
            q.push({1, r, c});
        }
        else{
            dist2_[r][c] = 0;
            q.push({2, r, c});
        }
    }

    while (!q.empty()){
        auto [d, r, c] = q.front(); q.pop();
        int nr = r, nc;
        if (nr & 1) nc = c - 1;
        else nc = c + 1;
        if (d == 1){
            if (nr & 1){
                if (nc == -1) ++nr, ++nc;
            }
            else{
                if (nc == M1) ++nr, --nc;
            }
            if (nr == N1) nr = nc = 0;
        }
        else{
            if (nr & 1){
                if (nc == -1) ++nr, ++nc;
            }
            else{
                if (nc == M2) ++nr, --nc;
            }
            if (nr == N2) nr = nc = 0;
        }
        if (d == 1){
            if (dist1_[nr][nc] > dist1_[r][c] + 1){
                dist1_[nr][nc] = dist1_[r][c] + 1;
                q.push({d, nr, nc});
            }
        }
        else{
            if (dist2_[nr][nc] > dist2_[r][c] + 1){
                dist2_[nr][nc] = dist2_[r][c] + 1;
                q.push({d, nr, nc});
            }
        }
    }

    if (dist1_[0][0] == 0){
        cout << "hing...";
        return 0;
    }

    // 정민이의 시작 위치부터 BFS 시작
    int dist1[N1][M1]; fill(&dist1[0][0], &dist1[N1 - 1][M1], inf); // 차원 1
    int dist2[N2][M2]; fill(&dist2[0][0], &dist2[N2 - 1][M2], inf); // 차원 2
    dist1[0][0] = 0;
    q.push({1, 0, 0});

    // 항상 블랙홀이 도달하는 시간보다 더 일찍 도착해야 한다.
    while (!q.empty()){
        auto [d, r, c] = q.front(); q.pop();
        if (d == 1 && R1 <= r && r < R1 + A && C1 <= c && c < C1 + B){ // 차원 1에서 게이트를 이용할 수 있다.
            int nr = R2 + r - R1, nc = C2 + c - C1;
            if (dist2[nr][nc] > dist1[r][c] + 3 && dist2_[nr][nc] > dist1[r][c] + 3){
                dist2[nr][nc] = dist1[r][c] + 3;
                q.push({2, nr, nc});
            }
        }
        if (d == 2 && R2 <= r && r < R2 + A && C2 <= c && c < C2 + B){ // 차원 2에서 게이트를 이용할 수 있다.
            int nr = R1 + r - R2, nc = C1 + c - C2;
            if (dist1[nr][nc] > dist2[r][c] + 3 && dist1_[nr][nc] > dist2[r][c] + 3){
                dist1[nr][nc] = dist2[r][c] + 3;
                q.push({1, nr, nc});
            }
        }

        // 상하좌우 이동
        if (d == 1){
            for (auto [dr, dc]: dir){
                if (0 <= r + dr && r + dr < N1 && 0 <= c + dc && c + dc < M1 && dist1[r + dr][c + dc] > dist1[r][c] + 1 && dist1_[r + dr][c + dc] > dist1[r][c] + 1){
                    dist1[r + dr][c + dc] = dist1[r][c] + 1;
                    q.push({d, r + dr, c + dc});
                }
            }
        }
        else{
            for (auto [dr, dc]: dir){
                if (0 <= r + dr && r + dr < N2 && 0 <= c + dc && c + dc < M2 && dist2[r + dr][c + dc] > dist2[r][c] + 1 && dist2_[r + dr][c + dc] > dist2[r][c] + 1){
                    dist2[r + dr][c + dc] = dist2[r][c] + 1;
                    q.push({d, r + dr, c + dc});
                }
            }
        }
    }

    if (dist2[N2 - 1][M2 - 1] < inf) cout << dist2[N2 - 1][M2 - 1];
    else cout << "hing...";
}

• Python

import sys; input = sys.stdin.readline
from math import inf
from collections import deque
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

K, N1, M1, N2, M2 = map(int, input().split())
A, B = map(int, input().split())
R1, C1 = map(int, input().split())
R2, C2 = map(int, input().split())

# 블랙홀이 도달하는 거리 구하기
dist1_ = [[inf] * M1 for _ in range(N1)] # 차원 1
dist2_ = [[inf] * M2 for _ in range(N2)] # 차원 2
dq = deque()
for _ in range(K):
    d, r, c = map(int, input().split())
    if d == 1:
        dist1_[r][c] = 0
        dq.append((1, r, c))
    else:
        dist2_[r][c] = 0
        dq.append((2, r, c))

while dq:
    d, r, c = dq.popleft()
    nr = r
    if nr & 1:
        nc = c - 1
    else:
        nc = c + 1
    if d == 1:
        if nr & 1:
            if nc == -1:
                nr += 1; nc += 1
        else:
            if nc == M1:
                nr += 1; nc -= 1
        if nr == N1:
            nr = nc = 0
    else:
        if nr & 1:
            if nc == -1:
                nr += 1; nc += 1
        else:
            if nc == M2:
                nr += 1; nc -= 1
        if nr == N2:
            nr = nc = 0
    if d == 1:
        if dist1_[nr][nc] > dist1_[r][c] + 1:
            dist1_[nr][nc] = dist1_[r][c] + 1
            dq.append((d, nr, nc))
    else:
        if dist2_[nr][nc] > dist2_[r][c] + 1:
            dist2_[nr][nc] = dist2_[r][c] + 1
            dq.append((d, nr, nc))

if dist1_[0][0] == 0:
    print('hing...')
    exit()

# 정민이의 시작 위치부터 BFS 시작
dist1 = [[inf] * M1 for _ in range(N1)] # 차원 1
dist2 = [[inf] * M2 for _ in range(N2)] # 차원 2
dist1[0][0] = 0
dq.append((1, 0, 0))

# 항상 블랙홀이 도달하는 시간보다 더 일찍 도착해야 한다.
while dq:
    d, r, c = dq.popleft()
    if d == 1 and R1 <= r < R1 + A and C1 <= c < C1 + B: # 차원 1에서 게이트를 이용할 수 있다.
        nr = R2 + r - R1; nc = C2 + c - C1
        if dist2[nr][nc] > dist1[r][c] + 3 and dist2_[nr][nc] > dist1[r][c] + 3:
            dist2[nr][nc] = dist1[r][c] + 3
            dq.append((2, nr, nc))
    if d == 2 and R2 <= r < R2 + A and C2 <= c < C2 + B: # 차원 2에서 게이트를 이용할 수 있다.
        nr = R1 + r - R2; nc = C1 + c - C2
        if dist1[nr][nc] > dist2[r][c] + 3 and dist1_[nr][nc] > dist2[r][c] + 3:
            dist1[nr][nc] = dist2[r][c] + 3
            dq.append((1, nr, nc))

    # 상하좌우 이동
    if d == 1:
        for dr, dc in dir:
            if 0 <= r + dr < N1 and 0 <= c + dc < M1 and dist1[r + dr][c + dc] > dist1[r][c] + 1 and dist1_[r + dr][c + dc] > dist1[r][c] + 1:
                dist1[r + dr][c + dc] = dist1[r][c] + 1
                dq.append((d, r + dr, c + dc))
    else:
        for dr, dc in dir:
            if 0 <= r + dr < N2 and 0 <= c + dc < M2 and dist2[r + dr][c + dc] > dist2[r][c] + 1 and dist2_[r + dr][c + dc] > dist2[r][c] + 1:
                dist2[r + dr][c + dc] = dist2[r][c] + 1
                dq.append((d, r + dr, c + dc))

if dist2[N2 - 1][M2 - 1] < inf:
    print(dist2[N2 - 1][M2 - 1])
else:
    print('hing...')