[백준] 1414번 불우이웃돕기 (Python)

1414번: 불우이웃돕기

문제

다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.

다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.

다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력한다. 만약, 모든 컴퓨터가 연결되어 있지 않으면 -1을 출력한다.

 

과정

1. 최소 스패닝 트리 문제이므로 크루스칼 알고리즘을 이용해 풀어준다.
2. 아스키 코드값에 따라서 가중치와 좌표값을 입력받고 전체 가중치의 합 - 최소 가중치 를 구해서 최대 가중치를 구한다.

 

예제 입력

3
abc
def
ghi

예제 출력

40

 

풀이

import sys
input = sys.stdin.readline

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

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        parent[y] = x
    elif x > y:
        parent[x] = y

n = int(input())
graph = [list(input().rstrip()) for _ in range(n)]
parent = [i for i in range(n + 1)]
edges = []

result = 0
for i in range(n):
    for j in range(n):
        if graph[i][j] == 0:
            edges.append((0, i, j))
        else:
            if ord('a') <= ord(graph[i][j]) <= ord('z'):
                edges.append((ord(graph[i][j]) - ord('a') + 1, i, j))
                result += (ord(graph[i][j]) - ord('a') + 1)
            elif ord('A') <= ord(graph[i][j]) <= ord('Z'):
                edges.append((ord(graph[i][j]) - ord('A') + 27, i, j))
                result += (ord(graph[i][j]) - ord('A') + 27)
edges.sort()

cnt = 0
for cost, x, y in edges:
    if cost == 0:
        continue
    if find(x) != find(y):
        union(x, y)
        result -= cost
        cnt += 1

if cnt == n-1:
    print(result)
else:
    print(-1)

 

한 줄씩 해석해보기

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

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        parent[y] = x
    elif x > y:
        parent[x] = y

• Disjoint Set이란, 서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• Union-Find란, Disjoint Set을 표현할 때 사용하는 알고리즘
• find(x): 노드의 집합 번호는 루트 노드이므로, 루트 노드를 확인하여 같은 집합인지 확인한다.
• union(x, y): x, y의 루트 노드를 찾고 다르면 y를 x의 자손으로 넣어 두 트리를 합한다.

n = int(input())
graph = [list(input().rstrip()) for _ in range(n)]
parent = [i for i in range(n + 1)]
edges = []

• n만큼 랜선을 입력받고 저장해준다.
• 부모 리스트를 만들어준다.
• 간선을 저장할 리스트를 만든다.

result = 0
for i in range(n):
    for j in range(n):
        if graph[i][j] == 0:
            edges.append((0, i, j))
        else:
            if ord('a') <= ord(graph[i][j]) <= ord('z'):
                edges.append((ord(graph[i][j]) - ord('a') + 1, i, j))
                result += (ord(graph[i][j]) - ord('a') + 1)
            elif ord('A') <= ord(graph[i][j]) <= ord('Z'):
                edges.append((ord(graph[i][j]) - ord('A') + 27, i, j))
                result += (ord(graph[i][j]) - ord('A') + 27)
edges.sort()

• 결과값을 저장할 변수를 만들어준다.
• 그래프를 확인하면서 해당 값이 0이면 간선에 가중치 0 과 좌표를 넣어준다.
• ord를 활용해 아스키 코드로 해당 알파벳 값을 계산한다.
• 각 알파벳이 맞다면 가중치와 좌표를 넣어준다.
• 리스트를 정렬한다.

cnt = 0
for cost, x, y in edges:
    if cost == 0:
        continue
    if find(x) != find(y):
        union(x, y)
        result -= cost
        cnt += 1

• 간선의 개수를 세줄 cnt 변수를 만들어준다.
• 가중치와 좌표를 가져온다
• 가중치가 0이라면 스킵한다
• x와 y가 같은 집합이 아니라면 루트노드를 찾고 다르면 y를 x의 자손으로 넣어 두 트리를 합한다.
• 결과값에서 가중치를 빼준다.
• 간선의 개수를 올려준다.

if cnt == n-1:
    print(result)
else:
    print(-1)

• 간선의 개수가 n-1이면 결과를 출력한다.
• 그게 아니라면 -1을 출력한다.