파이썬 백준 1647번 : 도시 분할 계획

문제 

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

 

 

🏙️풀이

MST에서 가장 큰 간선 하나를 제거하면 되는 문제이다. 

쿠루스칼 알고리즘으로 풀었다. 

import sys
def find_set(x): #연결된 최고 조상 확인
    if p[x] != x:
        p[x] = find_set(p[x]) # path compression
    return p[x]

def union(x, y): #차수가 더 작은 트리가 차수가 더 큰 트리 밑으로 들어감
    if r[x] > r[y]:
        p[y] = x
    else:
        p[x] = y
        if r[x] == r[y]:
            r[y] += 1


V, E = map(int, sys.stdin.readline().split())
edges = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]
edges.sort(key=lambda x: (x[2])) # 가중치 기준으로 정렬
p = list(range(V+1))
r = [0] * (V+1) #차수를 저장할 배열
answer = []
cnt = 0


for s, e, w in edges:
    if find_set(s) != find_set(e): #사이클이 아닐때
        union(find_set(s), find_set(e)) #합치기
        answer.append(w)
        cnt += 1
        if cnt == V:
            break

print(sum(answer)-max(answer))

 

 

덧)

프림 알고리즘으로는 해결되지 않았다... 두 알고리즘이 어떻게 다른지 더 공부해야될 것같다

프림알고리즘 - 인접행렬 : 시간초과 

import sys

def Prim():
    dist=[10001]*N #dist배열 초기화
    #print(dist)
    dist[0]=0 #탐색을 시작할 index
    for i in range(N):
        min_cost=10001
        min_j=-1
        for j in range(N): #dist배열에서 가장 작은 값을 찾아서 이동
            if j not in visited and dist[j]<min_cost:
                min_cost=dist[j] #값 갱신
                min_j=j
        visited.add(min_j)#방문표시

        for k in Graph[min_j]: #min_j로 이동해서 더 짧은 거리가 있는지 확인 후 갱신
            if k[0] not in visited and k[1]<dist[k[0]]:
                dist[k[0]]=k[1]
                #print(dist[k])
    return sum(dist)-max(dist)



N,M=map(int,sys.stdin.readline().split())

#Graph : 인접리스트
Graph=[[] for _ in range(N)]
#print(Graph)
for _ in range(M):
    v1,v2,c=map(int,sys.stdin.readline().split())
    Graph[v1-1].append((v2-1,c))
    Graph[v2-1].append((v1-1,c))
visited=set() #방문처리를 위한 set
#print(Graph)
# for i in Graph:
#     print(i)
print(Prim())

 

프림 알고리즘 - 인접 행렬 (메모리초과)

import sys

def Prim():
    dist=[10001]*N #dist배열 초기화
    #print(dist)
    dist[0]=0 #탐색을 시작할 index
    for i in range(N):
        min_cost=10001
        min_j=-1
        for j in range(N): #dist배열에서 가장 작은 값을 찾아서 이동
            if j not in visited and dist[j]<min_cost:
                min_cost=dist[j] #값 갱신
                min_j=j
        visited.add(min_j)#방문표시

        for k in range(N): #min_j로 이동해서 더 짧은 거리가 있는지 확인 후 갱신
            if k not in visited and Graph[min_j][k]<dist[k]:
                dist[k]=Graph[min_j][k]
                #print(dist[k])
    return sum(dist)-max(dist)



N,M=map(int,sys.stdin.readline().split())

#Graph : 인접행렬만들기
Graph=[[10001]*N for _ in range(N)]
for _ in range(M):
    v1,v2,c=map(int,sys.stdin.readline().split())
    Graph[v1-1][v2-1]=c
    Graph[v2-1][v1-1]=c
visited=set() #방문처리를 위한 set

# for i in Graph:
#     print(i)
print(Prim())