백준 6501 - Hotel booking (Python)

문제 정보

• https://www.acmicpc.net/problem/6501
• 다익스트라, BFS

---

문제 정리

운전자는 매일 이동한 시간이 600분 이하가 되어야 하며, 날마다 이동이 끝나면 체인점 호텔이 있는 도시에서 쉴 수 있다. 이 조건을 만족시키면서 1번 도시 -> N번 도시까지 이동할 때, 소요 일수의 최소값을 구하는 문제이다.

---

풀이

전체 도시(N)는 최대 10,000개까지 가능하고, 체인점 호텔(H)은 최대 100개까지 가능하다. 일반 도시를 기준으로 탐색할 경우 너무 오래 걸리게 되므로 그래프를 간단하게 만들 필요가 있다.

시작점, 도착점에도 체인점 호텔이 세워져 있다고 생각하고, 모든 체인점 호텔 간 이동 시간을 체크한다. 이동 시간이 600분 이내라면 간선이 존재한다고 생각하는 방식으로 그래프를 체인점 호텔로만 구성되도록 정점 수를 줄일 수 있다. 그래프 재구성은 모든 체인점 호텔들을 각각 시작점으로 잡고 다익스트라를 H+2번 돌려 간선을 추출한 다음, 재구축한 그래프에 대해 BFS 탐색을 진행하여 소요 일수의 최소값을 구하면 된다.

런타임이 괴랄하다.

---

코드

# 백준 6501

import io
from collections import deque
import heapq

input = io.BufferedReader(io.FileIO(0), 1<<18).readline
INF = 10**8


def Dijkstra(V, graph, start):
    distance = [INF for _ in range(V+1)]
    pq = []
    distance[start] = 0
    heapq.heappush(pq, (0, start))

    while pq:
        curDist, curV = heapq.heappop(pq)
        if distance[curV] < curDist:
            continue

        for nextV, tempDist in graph[curV]:
            nextDist = curDist + tempDist
            if nextDist < distance[nextV]:
                distance[nextV] = nextDist
                heapq.heappush(pq, (nextDist, nextV))

    return distance


def BFS(N, graph, start):
    visited = [INF for i in range(N)]
    q = deque()
    q.append(start)
    visited[start] = 0

    while q:
        curV = q.popleft()

        for nextV in graph[curV]:
            if visited[nextV] == INF:
                q.append(nextV)
                visited[nextV] = visited[curV]+1
    
    return 0 if visited[N-1] == INF else visited[N-1]


def solve(N, H, M, graph, chain):
    chain.sort()
    revChain = dict()
    for i in range(H):
        revChain[chain[i]] = i

    # 체인점 호텔을 시작점으로 잡고 다익스트라 진행
    graph2 = [[] for _ in range(H)]
    for i in range(H):
        startV = chain[i]
        dist = Dijkstra(N, graph, startV)

        # 다른 체인점 호텔까지 600분 이내에 도달 가능한 경우 간선 추가
        for j in range(i+1, H):
            endV = chain[j]
            if dist[endV] <= 600:
                graph2[revChain[endV]].append(i)
                graph2[i].append(revChain[endV])

    # BFS로 재구축한 그래프에 대해 최단 거리 도출
    return BFS(H, graph2, 0) - 1


def main():
    while True:
        N = int(input())
        if N == 0:
            break
        H, *chain = map(int, input().split())
        chain.append(1)
        chain.append(N)
        M = int(input())
        graph = [[] for _ in range(N+1)]
        for _ in range(M):
            a, b, t = map(int, input().split())
            graph[a].append((b, t))
            graph[b].append((a, t))

        print(solve(N, H+2, M, graph, chain))


main()