[BOJ][🟡4][백준#16562] 친구비

문제 출처

BAEKJOON Online Judge #16562

문제

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다! 학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다. 준석이는 이제 모든 친구에게 돈을 주지 않아도 된다! 위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

입력

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N) 다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다.

출력

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.

예제

예제 1

입력

5 3 20
10 10 20 20 30
1 3
2 4
5 4

출력

20

예제 2

입력

5 3 10
10 10 20 20 30
1 3
2 4
5 4

출력

Oh no

My Sol

import sys
input = sys.stdin.readline
from collections import deque

def bfs(i):
    global v
    Q = deque()
    Q.append(i)

    minMuch = much[i]
    while Q:
        u = Q.popleft()
        minMuch = min(minMuch, much[u])
        if v[u]: continue
        v[u] = 1

        for e in G[u]:
            Q.append(e)

    return minMuch

N, M, k = map(int, input().split())
much = [0]
much += list(map(int, input().split()))
G = [[] for _ in range(N+1)]
v = [0]*(N+1)
for _ in range(M):
    s, e = map(int, input().split())
    G[s].append(e)
    G[e].append(s)

minSsum = 0
for i in range(1, N+1):
    if not v[i]:
        minSsum += bfs(i)

ans = minSsum if minSsum <= k else 'Oh no'
print(ans)

그래프를 이용하는 문제일 것 같은데, BFS로도 풀 수 있을 것 같아서 잘 풀어낸 것 같다. visit 배열을 두고, 1부터 N까지 순회하며 visit 체크가 되어있지 않은 노드가 있다면 해당 노드와 연결된 모든 노드들을 visit체크해가며 최소 친구비를 구한다. bfs가 끝나면 전역에서 이 최소 친구비를 누적해간다.

전체 bfs를 모두 마치면 이때의 누적 값이 최소 친구비이며, 이를 k와 비교해서 k를 넘지 않는다면 누적값을 출력하고, k를 넘긴다면 종료한다.

결과

맞았습니다!!

모범답안

출처

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10000)


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


def union_(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return

    parent[a] = b
    arr[b] = min(arr[a], arr[b])


N, M, K = map(int, input().split())

parent = [i for i in range(N + 1)]

arr = [0] + list(map(int, input().split()))
for _ in range(M):
    a, b = map(int, input().split())
    union_(a, b)

ans = 0

for i in range(1, N + 1):
    if parent[i] == i:
        ans += arr[i]

if ans > K:
    print('Oh no')
else:
    print(ans)

유니온파인드를 이용해 방문한 노드는 한 루트노드로 간주하여 처음에 초기화하였듯이 parent가 인덱스 그 자신인 경우 방문하지 않은 경우이므로 유니온파인드를 실행하면 해당 인덱스의 친구비를 ans에 더해준다.

간선의 입력을 받을 때마다 union을 진행해 서로소 집합으로 묶어주고, 그 과정에서 해당하는 루트 노드 인덱스 b를 인덱스로 하는 arr 배열에 최소값을 갱신해준다. 불필요한 중복 조회를 하지 않아도 되기 때문에 BFS보다는 연산속도가 더 빠른 것으로 보인다.