백준 33527 - 신촌 길찾기 서비스

해당 문제는 BFS로 접근했다가 실패해 Floyd-Warshall 기법으로 푼 문제입니다.

문제 설명

5개의 대학교에 $N$개의 버스 정류장이 있으며, 각 대학교는 자체적으로 $X$개의 버스 노선을 운영합니다. 서로 다른 대학교에서 운영하는 동일한 번호의 버스 노선은 서로 다른 노선이므로, 총 $5X$개의 고유한 버스 노선이 존재합니다.

문제 풀이

초기에는 BFS를 사용하여 $N \times N$ 크기의 버스 노선 정보를 기반으로 탐색하는 방식을 시도했습니다. 그러나 $N$의 최대 크기가 $100,000$으로 매우 크기 때문에, 이 방식은 비효율적이며 시간 초과가 발생합니다. 반면, $X$의 최대 크기는 $100$으로 상대적으로 작아, $X$를 기준으로 최적화하는 방법이 더 효율적임을 알 수 있습니다.

이를 해결하기 위해, 각 대학교의 버스 노선을 고유하게 변환하여 처리하였습니다. $new\_route\_number = route\_number + route\_index * X - 1$ 연산을 사용하여 각 대학교의 노선을 고유한 번호로 매핑했습니다.

1. 인접 행렬 초기화

$5X \times 5X$ 크기의 2D bus 행렬을 생성하여, 정류장 $i$에서 정류장 $j$로 이동할 때 필요한 최소 환승 횟수를 저장합니다. 각 버스 노선에서 직접 연결된 정류장은 환승 없이 이동 가능하므로 bus[i][j] = 1로 설정합니다.

2. Floyd-Warshall 알고리즘 적용

이제 Floyd-Warshall 알고리즘을 사용하여 모든 정류장 간 최소 환승 횟수를 계산합니다. 점화식은 다음과 같습니다: $bus[i][j] = min(bus[i][j], bus[i][k] + bus[k][j])$

여기서,

bus[i][j] : 정류장 $i$에서 정류장 $j$까지의 최소 환승 횟수
bus[i][k] + bus[k][j] : 정류장 $i$에서 $k$를 거쳐 $j$로 가는 경우

이 과정을 $5X$번 반복하여 모든 정류장 쌍 간의 최소 환승 횟수를 계산합니다.

3. 쿼리 처리

Floyd-Warshall 알고리즘이 끝난 후, 질문 수 $Q$를 입력받고, 각 질문마다 **출발 정류장 $U_i$와 도착 정류장 $V_i$**를 받습니다. 이미 구해둔 bus 행렬을 활용하여 $U_i$에서 $V_i$까지 가는 최소 환승 횟수를 찾고 출력합니다.

시간 복잡도 분석

Floyd-Warshall 알고리즘의 시간 복잡도는 **$O(V^3)$**이며, 여기서 $V = 5X$이므로 전체 시간 복잡도는: $O(5X^3) = O(X^3)$ 따라서, $N$이 커도 $X$가 작기 때문에 충분히 효율적인 방식입니다.

코드

import sys
input = sys.stdin.readline

N, X = map(int, input().split())
routes = [[r + j * X - 1 for j, r in enumerate(map(int, input().split()))] for _ in range(N)]
sz, INF = 5*X, float('inf')
bus = [[0 if i == j else INF for j in range(sz)] for i in range(sz)]

for r in routes:
    for i in r:
        for j in r:
            if i != j:
                bus[i][j] = 1
# Floyd-Warshall Algorithm
for k in range(sz):
    for i in range(sz):
        if bus[i][k] < INF:
            for j in range(sz):
                bus[i][j] = min(bus[i][j], bus[i][k] + bus[k][j])

Q = int(input())
for _ in range(Q):
    u, v = map(lambda y: y - 1, map(int, input().split()))
    res = min((bus[i][j] for i in routes[u] for j in routes[v]), default=INF)
    sys.stdout.write(f'{res + 1 if res < INF else -1}\n')