김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1414 불우이웃돕기 파이썬(Python)

문제 링크

최소 스패닝 트리(Minimum Spanning Tree, MST) 문제.
크게 어렵지는 않고, 다만 입력이 연결 그래프가 아닌(즉, 여러개의 연결 요소로 된) 그래프일 수 있다는 점과, 입력이 조금 익숙하지 않은 형태로 들어온다는 점만 주의하면 된다.
입력의 경우, 인접 행렬(Adjacency Matrix)의 형태로 들어오는데, graph[i][j] != graph[j][i]일 수 있다.
즉, 두 개의 노드 사이에 최대 두 개의 간선이 존재할 수 있다는 것을 의미한다.
또한, 간선의 가중치가 알파벳 문자열로 주어지기 때문에, ord() 함수를 이용해 아스키 정수로 변환한 후 적절한 연산을 수행할 필요가 있다.
이후, 유니온 파인드(Union-Find, Disjoint Set) 기반의 크루스칼 알고리즘을 수행하면 되는데, 유니온 횟수를 temp 변수에 저장해서, temp == n - 1인지 확인해야 한다. 유니온 횟수는 결국 사용하는 간선의 개수가 되고, 트리에서 간선의 개수는 n - 1개 이므로, 모든 노드가 연결되도록 트리가 구성되었다면 temp == n - 1이 될 것이다.

#!python

from sys import stdin
input = stdin.readline

# 파인드
def root(node):
    if parent[node] != node:
        parent[node] = root(parent[node])
    return parent[node]

# 유니온
def union(a, b):
    ra, rb = root(a), root(b)
    parent[ra] = parent[rb] = min(ra, rb)

# edges: 엣지 리스트
# parent: 유니온 파인드 위한 부모 리스트
# ans: 기부할 수 있는 총 길이
# temp: 연결한 랜선 개수
n = int(input())
edges = []
parent = [i for i in range(n)]
ans = 0
temp = 0

# 인접 행렬 파싱
for i in range(n):
    for j, e in enumerate(input().strip()):
        if e == '0':
            continue
        # ord('a') = 97
        # ord('A') = 65
        # ans는 전체 랜선 길이가 된다
        if ord(e) >= 97:
            w = ord(e) - 96
        else:
            w = ord(e) - 38
        edges.append((w, i, j))
        ans += w

# 크루스칼 알고리즘
# ans에 전체 랜선 길이가 있으므로 연결한 랜선 길이만큼 빼준다
edges.sort()
for w, a, b in edges:
    if root(a) == root(b):
        continue
    temp += 1
    ans -= w
    union(a, b)

# temp가 n - 1이라는 것은 n - 1개 랜선을 사용했다는 뜻
if temp == n - 1:
    print(ans)
else:
    print(-1)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑