27945 슬슬 가지를 먹지 않으면 죽는다 (백준, python3)

 

시간 제한	메모리 제한
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()