[백준/python3] 15808번 : 주말 여행 계획

https://www.acmicpc.net/problem/15808

---

알고리즘 분류

• 그래프 이론
• 데이크스트

문제

영선이는 요즘 여행에 빠져있다. 그래서 짧게나마 여행을 다녀오고 싶었던 영선이는 주말을 활용해 여행 갈 계획을 세우고 있다. 하지만 영선이는 가고 싶은 여행지가 너무 많아 고민 중이며, 숙소 또한 좋은 곳으로 가고 싶기에 여행지와 숙소를 기반으로 계획을 작성하려 한다.

영선이는 가고 싶은 여행지 리스트와 숙소 리스트를 미리 조사하여 작성했다. 그리고 각 여행지와 숙소에 조사한 자료를 통해 기대치를 매겼다. 시간이 없기에 영선이는 여행지 한 곳, 숙소 한 곳을 방문할 것이며, 이때 선택된 장소들의 기대치 합이 최대가 되는 여행 계획을 작성할 것이다.

또한, 여행지와 숙소 사이의 거리가 멀다면 여행지에서 관광을 하는 시간이 줄어들기 때문에, 여행 자체의 재미가 줄어든다고 생각했다. 결국 영선이는 기대치 합에서 둘 사이 거리를 빼기로 하였다.

즉, 여행 계획은 여행지, 숙소 각각의 기대치의 합에서 둘 사이의 거리를 뺀 값을 최대로 하는 계획을 작성하려고 한다. 하지만 어떤 문제나 그렇듯 영선이는 매우 바쁜 관계로 계획을 세울 시간이 없다. 그렇기 때문에 계획을 세우는 것을 당신에게 부탁했다. 영선이가 작성한 여행지와 숙소 리스트 및 인근 지역의 지도를 토대로 영선이의 주말 여행 계획을 세워주자.

입력

프로그램의 입력은 표준 입력으로 받는다. 여행을 하고자 하는 지역의 지도는 다음과 같은 정보가 주어진다. 주요 지점들 n개와 그 사이를 연결하는 도로가 주어지고, 도로에는 거리가 표기되어 있다. 여행지와 숙소들은 각각 한 지점에 표기되어 있으며, 여행지와 숙소는 같은 지점에 위치해 있지 않는다. 그리고 모든 지점들은 다른 지점으로 도로를 통하여 이동할 수 있는 경로가 존재한다.

입력의 첫 줄에는 지점의 개수 n이 주어진다. (2 ≤ n ≤ 1000)

다음 n줄에는 각 줄마다 n개의 정수가 주어지며, i번째 줄의 j번째 수 dij 는 i번째 지점에서 j번째 지점까지의 거리이다. 만약 거리가 0이라면 둘 사이의 도로는 존재하지 않는다(0 ≤ dij ≤ 5000, dij = dji , dii = 0)

다음 줄에는 리스트에 작성된 여행지의 개수 p, 숙소의 개수 q가 주어진다. (1 ≤ p,q ≤ n, 2 ≤ p+q ≤ n)

다음 p줄에는 여행지가 위치한 지점번호 lj 과 기대치 wj 가 주어진다.(1 ≤ lj ≤ n, 1 ≤ wj ≤ 5000)

다음 q줄에는 숙소가 위치한 지점번호 li 과 기대치 wi 가 주어진다.(1 ≤ li ≤ n, 1 ≤ wi ≤ 5000)

출력

프로그램의 출력은 표준 출력으로 한다. 여행지와 숙소의 쌍 중 각각의 기대치의 합에서 둘 사이의 거리를 뺀 값이 최대가 되는 값을 출력하시오. 이때, 여행지와 숙소 사이의 경로에 다른 여행지나 숙소가 존재해도 무방하다.

입출력 예제

---

풀이

 시간 복잡도에 신경을 쓰면서 풀어야 했던 문제다. 다익스트라인걸 알고 접근을 하였으나, 사실 처음에 짰던 코드는 플루이드-워셜 알고리즘으로 구현했다. 플루이드-워셜 알고리즘의 시간 복잡도는 O(n^3)인데 n=1000이니...

그 다음에는 다익스트라로 접근하였다. 우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용하지 않는 경우의 시간 복잡도는 O((V+E)logV)인데 (V : 정점, E : 간선), 만약 E가 최대치에 가까우면 어떻게 될까? E=n(n-1)/2, V=n. 즉 O(n^2*logn)의 시간 복잡도가 된다.

그러므로 여기서는 배열 내에서 선형탐색 + 배열 내에 중복 정점 허용하지 않는 방식으로 구현한다. O(V^2+E)의 시간 복잡도이므로 O(2*n^2). 즉 O(n^2)의 시간 복잡도를 가지게 된다. 그러므로 여기서는 이 방식을 선택하여 구현을 해야한다.

---

코드

import heapq
import sys

input = sys.stdin.readline
MAX = float('inf')
ans = MAX
n = int(input())
adj = [list(map(int, input().strip().split())) for _ in range(n)]
p, q = map(int, input().strip().split())
tour = [tuple(map(int, input().strip().split())) for _ in range(p)]
hotel = [tuple(map(int, input().strip().split())) for _ in range(q)]
dist = [MAX] * n
visited = [False] * n # 중복 허용 없앰
pq = []

for x, y in tour:
    x -= 1
    dist[x] = -y
    heapq.heappush(pq, (dist[x], x))
    
cnt = [0] * n
for x, y in hotel:
    x -= 1
    cnt[x] = y

while pq:
    w, v = heapq.heappop(pq)
    if visited[v]:
        continue
    visited[v] = True
    for i in range(n): # 인접 행렬 선형 탐색
        if adj[v][i] == 0 or visited[i]:
            continue
        if dist[i] > adj[v][i] + w:
            dist[i] = adj[v][i] + w
            heapq.heappush(pq, (dist[i], i))

for i in range(n):
    if cnt[i]:
        ans = min(ans, dist[i] - cnt[i])
    
print(-ans)

---