[Python 3] BOJ - 16562 "친구비"

 # 문제 링크 : https://www.acmicpc.net/problem/16562

16562번: 친구비

 # 풀이 : 

 모든 친구와 친구관계를 맺어야 하는 것이 목표이다. 개인적으로 문제의 핵심은 친구의 친구는 친구라는 것이다. 따라서, 친구관계를 그래프로 본다면 친구관계가 끊어질 때 까지 속한 정점들을 담는다면 이는 하나의 연결 요소라고 할 수 있다.

예를 들어 아래 두개의 그래프를 생각해보자

<그림 1. 연결 그래프인 경우>

 그래프 1의 경우는 연결 그래프기 때문에 친구관계가 끊어지지 않는다. 따라서 1,2,3,4,5,6 중 어느 하나와 친구관계가 성립한다면 모두와 친구관계가 된다. 따라서 이 경우에는 전체 정점 중 가장 친구비가 싼 친구에게 친구비를 지급하면 된다.

 

<그림 2. 연결 그래프가 아닌 경우>

 그래프 2의 경우는 1,2,3으로 이루어진 연결 요소와 4,5,6,7로 이루어진 연결 요소로 나뉘게 된다. 따라서 {1, 2, 3} 집합 중 친구비가 가장 싼 친구에게 친구비를 주고 {4, 5, 6, 7} 집합 중 친구비가 가장 싼 친구에게 친구비를 주면 최소의 비용으로 모든 친구 관계를 맺을 수 있다.

 주의할 점은 아무리 최소비용을 구한다 하더라도 문제에서 주어진 예산의 범위를 벗어나면 모든 친구관계를 맺을 수 없으므로 문제의 출력조건에 따라 출력한다.

 

 # 코드

import sys

# Python 3의 기본재귀깊이가 1000이므로 재귀깊이를 해제한다
sys.setrecursionlimit(10 ** 9)

# 입력부
n,m,k = map(int, sys.stdin.readline().split())
money = list(map(int, sys.stdin.readline().split()))

# 인접리스트 생성
adj = [[] for _ in range(n)]

ans = []
for i in range(m):
    a,b = map(int, sys.stdin.readline().split())
    # 양방향 간선
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

# 방문 여부를 확인하는 배열
check = [False] * n

# dfs_list : 친구관계에 속하는 정점을 리턴하는 함수
def dfs_list(x, store):
    check[x] = True
    for i in adj[x]:
        if check[i] == False:
            store.append(i)
            dfs_list(i, store)
    return store

for i in range(n):
    # 만일 정점 i가 False라면 다른 연결 요소에 있기 때문에 dfs_list를 호출한다
    if check[i] == False :
        each = dfs_list(i, [i])
        temp = 999999999999
        # 정점 i와 친구관계인 정점들 중 가장 싼 친구비를 찾는다
        for j in each:
            if temp > money[j]:
                temp = money[j]
        # 연결요소의 최소비용을 정답배열에 추가한다
        ans.append(temp)

# 예산범위에 맞는지 확인한다
if sum(ans) <= k:
    print(sum(ans))
else:
    print('Oh no')