| 시간 제한 | 메모리 제한 |
| 1초 | 1024MB |
문제
입력
출력
첫째 줄에 d의 최댓값을 출력한다.
풀이
총 N-1개의 길만 골라야 한다. 모든 길의 정보를 받으면서 가장 먼저 여는 가게의 정보를 기억해둔다. 그 길에 연결된 학원부터 탐색을 시작한다.
학원 u를 탐색하기 시작하면 연결된 v들과 그 길 위에 t를 확인해 가장 먼저 여는 노점이 있는 길을 선택한다. 그런데 만약 v와 u가 이미 선택된 길들로 이동이 가능한 상태라면 선택하지 않는다. 만약 N-1개의 길을 잘 선택해서 N일까지 키위새가 죽지 않는다고 해보자. 도중에 어떤 탐색에서라도 u와 v가 이미 이동가능한 경로가 선택된 상태라면 사이클이 생겨나게 되고 N-1개의 길을 어떻게 선택하더라고 N개의 학원을 모두 갈 수 없게 된다. 문제에서 원하는 조건은 모든 학원을 방문할 수 있도록 길을 기억하는 것이기 때문에 이 부분은 유니온파인드로 거르도록 처리한다.
현재 선택된 학원들로 이어지는 길들 중, 가장 빨리 여는 노점을 찾는 건 우선순위 큐를 활용한다. 학원 u에서 학원 v로 이어지는 길을 선택하는 경우, v와 이어지는 학원들과 그 위의 노점들이 여는 날을 우선순위 큐에 저장한다. 저장할 때는 튜플의 맨 앞을 노점의 여는 날로 정해 가장 빨리 여는 노점을 먼저 확인하도록 한다.
우선순위 큐에서 꺼낸 노점의 양쪽 끝 학원이 이미 경로로 연결되었다면 탐색하지 않고 다음 노점을 확인한다. 연결되지 않았다면 두 학원을 연결하고, 해당 노점이 여는 날을 gaji 리스트에 저장한다.
탐색을 모두 마쳤다면 N-1개의 길을 선택한 것이 된다. gaji 리스트에는 N-1개의 노점의 여는 날이 저장되어있을 것이다. 이 리스트를 정렬해 맨 앞부터 확인하는데 맨 앞 값부터 각각 1, 2, 3, ...d인지 확인해보고 아닌 값이 등장하면 그 때 확인중이던 d가 키위새가 죽는 날이 된다.
(내가 짠 코드는 매우 비효율적인 코드로 걸린 시간으로 파이썬 꼴찌임.)
정답 코드
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def solution():
n, m = map(int, input().split())
date = [dict() for _ in range(n + 1)]
link = [[] for _ in range(n + 1)]
start = 0
early = int(1e9)
for _ in range(m):
u, v, t = map(int, input().split())
if t < early:
early = t
start = u
date[u][v] = t
date[v][u] = t
link[u].append(v)
link[v].append(u)
head = [i for i in range(n + 1)]
def union(a, b):
A = find(a)
B = find(b)
if A == B:
return False
elif A < B:
head[B] = A
else:
head[A] = B
return True
def find(k):
while head[k] != k:
k = head[k]
return k
hq = []
gaji = [0, int(1e9)]
edge = 1
for next in link[start]:
heappush(hq, (date[start][next], next, start))
while hq and edge < n:
k, now, before = heappop(hq)
if union(now, before):
gaji.append(k)
edge += 1
for next in link[now]:
if find(now) == find(next): continue
heappush(hq, (date[now][next], next, now))
gaji.sort()
for i in range(1, len(gaji)):
if gaji[i] == i: continue
else:
print(i)
break
solution()
