[백준]1647 도시분할계획

1.풀이

(1) 2개의 연결된 그래프를 만들기 위해선 크루스칼 알고리즘을 적용한 뒤 가장 큰 간선을 하나 빼면된다.

이때 가장 큰 간선은 N-1번째에 들어오는 간선이므로, 2개의 mst를 만들기 위해선 간선을 N-2번째까지 추가해 주면 된다.

 

(2) 최소간선부터 하나씩 넣어볼 때, pq를 쓰는방법과 sort를 하고 앞에서부터 뽑는 방법이 있다. 결과는 아래와 같다.

< sort >

소스코드1 : edge.pop(0)을 해줌 ->시간초과

소스코드2 : edge[i]로 참조해줌 -> 통과 (5696ms)

< pq >

소스코드3 : heapq.heappop() -> 통과 (6992ms)

*pq는 매번 pop하고 정렬해주어야 하기 때문에 한번 정렬 후 앞에서 부터 참조하면 되는 소트보다 느림

단, 소트후 앞에서부터 참조할 때 pop을 쓰면 오히려 시간초과가 나기 때문에 주의.

​

2.소스코드

(1) 소스코드1 (sort, edge.pop(0) 시간초과)

import sys
N,M=map(int,input().split())
edge=[]
for i in range(M):
    a,b,c=map(int, sys.stdin.readline().rstrip().split())
    edge.append([c,a,b])
edge.sort()
parent=[i for i in range(N+1)]

#루트노드 찾기
def find(a):
    if a==parent[a]:
        return a
    else:
        parent[a]=find(parent[a])
        return parent[a]
def union(a,b):
    a=find(a)
    b=find(b)
    parent[b]=a

ans=0
cnt=0
for i in range(M):
    c,a,b=edge.pop(0)
    if not find(a)==find(b):
        ans+=c
        union(a,b)
        cnt+=1
    if cnt==N-2:
        break
print(ans)

 

(2) 소스코드2 (sort, edge[i] 통과)

import sys
N,M=map(int,input().split())
edge=[]
for i in range(M):
    a,b,c=map(int, sys.stdin.readline().rstrip().split())
    edge.append([c,a,b])
edge.sort()
parent=[i for i in range(N+1)]

#루트노드 찾기
def find(a):
    if a==parent[a]:
        return a
    else:
        parent[a]=find(parent[a])
        return parent[a]
def union(a,b):
    a=find(a)
    b=find(b)
    parent[b]=a

ans=0
cnt=0
for i in range(M):
    c,a,b=edge[i]
    if not find(a)==find(b):
        ans+=c
        union(a,b)
        cnt+=1
    if cnt==N-2:
        break
print(ans)

 

(3) 소스코드3 (heapq.heappop() 통과)

import sys
import heapq

N,M=map(int,input().split())
edge=[]
for i in range(M):
    a,b,c=map(int, sys.stdin.readline().rstrip().split())
    heapq.heappush(edge,[c,a,b])
parent=[i for i in range(N+1)]

#루트노드 찾기
def find(a):
    if a==parent[a]:
        return a
    else:
        parent[a]=find(parent[a])
        return parent[a]
def union(a,b):
    a=find(a)
    b=find(b)
    parent[b]=a

ans=0
cnt=0
for i in range(M):
    c,a,b=heapq.heappop(edge)
    if not find(a)==find(b):
        ans+=c
        union(a,b)
        cnt+=1
    if cnt==N-2:
        break
print(ans)