[알고 스터디] 7. 최단 거리 알고리즘 - 1647

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

1647번: 도시 분할 계획

도시 분할 계획 - 🥇4

---

[1] 풀이 및 생각

처음엔 진짜 그냥 자료구조 없이!! 풀어보고 싶어서 초초 무식한 방법을 썼다.

그래서 생각해보면 가능은 한 코드인데 저어얼대 시간내 못풀코드 ㅋㅋ

 

하나씩 받는데, 큰 weight의 간선부터 처리하는데 하나씩 지우면서 마을이 2개이상으로 갈라지는지 확인하고, 최초로 순환이 없어지는 순간까지 찾아가는 방식으로 푼 것같다. 근데 진짜 오래걸려서 이건 아닌거같고 ㅋㅋㅋ ㅠㅠ (테케까진 맞는데,,,)

 

그래서 스터디 이후에 내가 여러 MST 관련 알고리즘을 배우고 이제야 제대로 알았다!!

프림, 크루스칼, 다익스트라 등등을 배우면서

 

이 문제는 프림/크루스칼로 MST 만든후에 제일 긴걸짜른다!!! <- 진자 개똑똑하다 ㄷㄷ 어케하누

사실 쉬운 접근일수도있는데 스터디 중간에 MST가 뭔지 알았음 ㅎ.. (얘들아 미안)

 

근데 Prim 알고리즘으로 먼저 풀었는데 이건 시간초과가 뜨더라,,!!

Kruskal 알고리즘은 되던데,, 흐음 나의 얕은 식견으로 생각하자면 따라가는거 보다 우순큐로 가중치가 낮은거만 보는게 더 빨라서 ㄱ런게 아닐까,,? 싶긴하다.

[2] 코드

import heapq
import collections
import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # 노드 수, 간선 수
graph = collections.defaultdict(list) # 빈 그래프 생성
visited = [0] * (n+1) # 노드의 방문 정보 초기화

# 특정 원소가 속한 집합을 찾기
def find(parent, x):
    if parent[x] == x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기 (간선 연결)
def union(parent, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)
    if rootA < rootB:
        parent[rootB] = rootA
    else:
        parent[rootA] = rootB

parent = [0] * (n + 1)
edges = []
result = 0
max_wt = 0 # 가장 큰 weight를 끊어서 두 개의 마을로 분할

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, n + 1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(m):
    a, b, cost = map(int, input().split())
    # 비용순으로 오름차순 정렬하기 위해 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((cost, a, b))

# edges.sort()
heapq.heapify(edges)

while edges:
    cost, a, b = heapq.heappop(edges)
    # 사이클이 발생하지 않는 경우에만
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        result += cost
        if max_wt < cost:
            max_wt = cost
print(result - max_wt)

import heapq
import collections
import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # 노드 수, 간선 수
graph = collections.defaultdict(list) # 빈 그래프 생성
visited = [0] * (n+1) # 노드의 방문 정보 초기화

# 프림 알고리즘 구현
# # 무방향 그래프 생성
# for i in range(m): # 간성 정보 입력 받기
#     u, v, weight = map(int, input().split())
#     graph[u].append([weight, u, v])
#     graph[v].append([weight, v, u])
#
# # 프림 알고리즘
# def prim(graph, start_node):
#     visited[start_node] = 1 # 방문 갱신
#     candidate = graph[start_node] # 인접 간선 추출
#     heapq.heapify(candidate) # 우선순위 큐 생성
#     # mst = [] # mst
#     total_weight = 0 # 전체 가중치
#     max_mst_weight = 0
#
#     while candidate:
#         weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
#         if visited[v] == 0: # 방문하지 않았다면
#             visited[v] = 1 # 방문 갱신
#             # mst.append((u, v, weight)) # mst 삽입
#             total_weight += weight # 전체 가중치 갱신
#             if max_mst_weight < weight:
#                 max_mst_weight = weight
#
#             for edge in graph[v]: # 다음 인접 간선 탐색
#                 if visited[edge[2]] == 0: # 방문한 노드가 아니라면, (순환 방지)
#                     heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입
#
#     return total_weight, max_mst_weight

# res_weight, max_weight = prim(graph, 1)
# print(res_weight - max_weight)

[3] 시간복잡도 계산

- 입력받는 부분 : O(n)

- 간선 처리 부분 : O(mlogn) = heapq.heapify-heappop을 통해서 연산하면 각 간선마다 O(logm)임 * m개

- 총 시간복잡도 : O(n) + O(mlogm) -> O(mlogm)