[백준] 1647번 도시 분할 계획 _ Python

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

1647번: 도시 분할 계획

 

 

---

 

1. Preview

시간 복잡도: O(M*logM)

 

공간 복잡도: O(M)

 

참고 : -

 

유형: MST

 

 

---

 

2. 초기 접근 방법

MST(Minimum Spanning Tree) 알고리즘
그래프 내의 모든 정점을 포함하는 트리를 구성하는데, 구성 간선들의 가중치 합의 최소를 목표로 한다.

 

 

프림 알고리즘

: 방문한 노드의 미방문 노드 간선들 중 최소 간선을 선택

 

-

heap 자료구조를 사용해, 미방문 노드 간선들 중 최소 간선 정보를 유지한다.

while pq:
    # 연결된 간선들 중 최소 간선을 pop한다.
    cost, now = heapq.heappop(pq)

    if not visited[now]:
        visited[now] = True
        costList.append(cost)

        if len(costList) == N:
            break
        for dist, end in graph[now]:
            if not visited[end]:
                # 연결된 간선들 중 미방문 노드 간선을 모두 heap에 넣는다.
                heapq.heappush(pq, (dist, end))

 

 

 

크루스칼 알고리즘

: 간선들을 cost 오름차순으로 정렬한 뒤, 사이클을 형성하지 않는 선에서 순서대로 간선을 선택

 

-

find() : 사이클 여부 판단

union() : 연관 관계 지정 (연관 노드는 동일한 부모 설정)

def find(x):
    if parent[x] == x:
        return x

    return find(parent[x])

def union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX < rootY:
        parent[rootY] = rootX
    else:
        parent[rootX] = rootY


# 초기 부모 노드는 자기 자신으로 설정
parent = [0 for _ in range(N+1)]
for i in range(1, N+1):
    parent[i] = i

# 최소 간선부터 선택하기 위함
edges.sort()

result = []
for cost, start, end in edges:
    # 부모 노드가 서로 다를 시
    # 즉, 사이클을 형성하지 않을 시
    if find(start) != find(end):
        union(start, end)

        result.append(cost)
        if len(result) == N-1:
            break

 

 

---

 

3. 생각

 

프림 알고리즘을 구현하고, 코드 리뷰를 할 때 문득 "10번째 if문 조건처리가 필요한가?" 라는 생각이 들었다.

어차피 17번째 라인에서 현재 노드와 연결된 간선들을 추가할 때, '미방문 노드 간선'만을 heap에 넣어준다.

따라서 heap에서 pop을 할 때 방문 여부를 체크하지 않아도 되지 않을까? 했다..

 

고민에 대한 정답을 먼저 말하자면 10번째 if문 조건처리가 필요하다.

간단히 예시를 들어보면

프림 최소 간선으로 사용하여 True가 되었음에도, heap에 남아있는 간선 때문에 costList에 다시 추가될 수도 있다.

def prim():
    pq = [] # 간선(거리, 시작 노드) 저장
    heapq.heappush(pq, (0, 1))

    costList = []
    while pq:
        # 연결된 간선들 중 최소 간선을 pop한다.
        cost, now = heapq.heappop(pq)

        if not visited[now]: ## 이 라인이 필요한가??
            visited[now] = True
            costList.append(cost)

            if len(costList) == N:
                break
            for dist, end in graph[now]:
                if not visited[end]:
                    # 연결된 간선들 중 미방문 노드 간선을 모두 heap에 넣는다.
                    heapq.heappush(pq, (dist, end))

    return sum(costList) - max(costList)

 

 

+.

그리고 당연한 개념이지만 무심코 넘어갈 수 있는 개념이 있다.

프림이나 다익스트라 알고리즘처럼 heap(우선순위 큐)을 사용하는 알고리즘은 기본적으로 그리디 패러다임 알고리즘이다.

이는 heap에 넣을 때는 우선순위가 정해지지 않을 수 있지만 heap에서 뺄 때는 항상 우선순위가 정해져 있음을 의미한다.

따라서 임의의 원소 k가 heap에 처음 들어갈 때 방문처리 하는 것이 아니라, heap에서 처음 나갈 때 방문처리를 해야 한다.

 

 

---

 

4. 코드

 

1) 프림 알고리즘 (5088ms)

import heapq
import sys
input = sys.stdin.readline

def prim():
    pq = [] # 간선(거리, 시작 노드) 저장
    heapq.heappush(pq, (0, 1))

    costList = []
    while pq:
        # 연결된 간선들 중 최소 간선을 pop한다.
        cost, now = heapq.heappop(pq)

        if not visited[now]:
            visited[now] = True
            costList.append(cost)

            if len(costList) == N:
                break
            for dist, end in graph[now]:
                if not visited[end]:
                    # 연결된 간선들 중 미방문 노드 간선을 모두 heap에 넣는다.
                    heapq.heappush(pq, (dist, end))

    return sum(costList) - max(costList)



# 집의 개수, 길의 개수
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [False for _ in range(N + 1)]

for _ in range(M):
    s, e, c = map(int, input().split())
    graph[s].append((c, e))
    graph[e].append((c, s))

print(prim())

 

 

 

2) 크루스칼 알고리즘 (3512ms)

import sys
input = sys.stdin.readline

def find(x):
    if parent[x] == x:
        return x

    return find(parent[x])

def union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX < rootY:
        parent[rootY] = rootX
    else:
        parent[rootX] = rootY


# 집의 개수, 길의 개수
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [False for _ in range(N + 1)]

edges = []
for _ in range(M):
    s, e, c = map(int, input().split())
    edges.append((c,s,e))

# 초기 부모 노드는 자기 자신으로 설정
parent = [0 for _ in range(N+1)]
for i in range(1, N+1):
    parent[i] = i

# 최소 간선부터 선택하기 위함
edges.sort()

result = []
for cost, start, end in edges:
    # 부모 노드가 서로 다를 시
    # 즉, 사이클을 형성하지 않을 시
    if find(start) != find(end):
        union(start, end)

        result.append(cost)
        if len(result) == N-1:
            break

# 마을 분리
print(sum(result) - max(result))