Boj 1922 - [네트워크 연결] (feat. Python)

[네트워크 연결]

1922번: 네트워크 연결

 

접근 방법

Union - Find 접근

• 두 노드 A와 B가 같은 부모 노드를 가지는지 검사(Find)하고
• 서로 다른 부모를 가질 경우, 두 노드를 합치고 부모 노드를 통일해준다(Union)

 

문제 접근

1. 전체 간선을 담을 리스트 형식의 자료구조를 준비한다.
2. 배열을 간선이 작은 순서대로 정렬한다
   • 이유는 A와 B를 연결하는 여러 간선 중에 가장 작은 간선이 먼저 배치되어야하기 때문이다
3. 간선 리스트 자료구조에 대해 분기문을 돌면서 간선의 두 컴퓨터 A와 B의 네트워크가 같은지 검사한다 (Find)
4. 두 노드의 컴퓨터의 네트워크가 다르면, 네트워크를 연결하고(Union) 두 컴퓨터 간의 거리를 결과 값에 더한다

 

문제 시각화

1. 초기 컴퓨터의 네트워크 연결 상태

2. 간선의 길이가 가장 짧은 1을 기준으로 네트워크 연결

3. 그 다음으로 작은 길이인 2를 기준으로 네트워크 연결 후 불필요 간선 제거

4. 그 다음으로 작은 길이인 3을 기준으로 연결 후 불필요 간선 제거

5. 마지막으로 연결 된 네트워크 중 가장 긴 길이인 4를 기준으로 모든 컴퓨터를 하나의 네트워크로 연결

 

 

Code

# 같은 네트워크인지 검사
def find_network(network, x):
    if network[x] != x:
        network[x] = find_network(network, town[x])

    return network[x]

# 네트워크를 합친다
def union_network(network, a, b):
    a = find_network(network, a)
    b = find_network(network, b)
    if a < b:
        network[b] = a
    else:
        network[a] = b


n = int(input())
m = int(input())

network = [0] * (n+1)
edges = []

# 초기 각각의 네트워크는 연결이 되어있지 않다
for i in range(1, (n+1)):
    network[i] = i

# 입력 값으로 연결 된 네트워크를 기록한다
for _ in range(m):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

# 네트워크 길이를 오름차순으로 정렬한다. 그 이유는 최솟값을 구하기 때문이다
edges.sort()
last = 0

result = 0

for edge in edges:
    cost, a, b = edge
    # 같은 네트워크에 속하지 않으면 두 네트워크를 묶어준다
    if find_network(network, a) != find_network(network, b):
        union_network(network, a, b)
        # 결과값에 더해준다
        result += cost

print(result)