[백준] 16562 - 친구비

1. 문제

16562번: 친구비

2. 개요

학생 N명이 있고 각 학생들간의 친구관계가 주어진다.

각 학생들과 친구가 되기 위해서는 각각 친구비가 필요하다.

친구의 친구는 친구다 라는 방식(A와 친구라면, A와 친구인 모든 사람은 친구)을 이용하여 모든 친구를 사귀는 경우의 최소 비용을, 모든 친구를 사귈 수 없다면 “Oh no”를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

일단 그래프를 양방향이 되도록 이어준다.

학생 한 명씩 dfs를 실행하는데, 탐색한 학생이 아닌 경우에만 실행하고, 최초실행시 그룹을 생성하여 비용을 넣어간다.

모든 탐색이 끝났다면, 각 그룹들을 탐색하며 최소비용만 뽑아내여 더한 후 결과를 확인, 출력한다.

3-2. Python

import sys

sys.setrecursionlimit(1000000000)

def dfs(n):
    for next in graph[n]:
        if visited[next] == 0:
            visited[next] = 1
            groups[-1].append(costs[next-1])
            dfs(next)

N, M, k = map(int, sys.stdin.readline().split())

costs = list(map(int, sys.stdin.readline().split()))
visited = [0 for i in range(N+1)]
graph = [[] for _ in range(N+1)]

for i in range(M):
    v, w = map(int, sys.stdin.readline().split())

    graph[v].append(w)
    graph[w].append(v)

groups = []

for i in range(1, N+1):
    if visited[i] == 0:
        groups.append([costs[i-1]])
        visited[i] = 1
        dfs(i)

answer = 0

for group in groups:
    answer += min(group)

    if answer > k:
        answer = "Oh no"
        break

print(answer)

3-3. C#

internal class Program
{
    static string[] input;
    static int[] costs;
    static int[] visited;
    static int[][] graph;
    static List<int[]> groups;
    static void Main(string[] args)
    {
        input = Console.ReadLine().Split();

        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);
        int k = int.Parse(input[2]);
        
        costs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        visited = new int[N + 1];
        graph = new int[N + 1][];

        for (int i = 0; i < N + 1; i++)
        {
            graph[i] = new int[] { };
        }

        for (int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split();
            int v = int.Parse(input[0]);
            int w = int.Parse(input[1]);

            graph[v] = graph[v].Append(w).ToArray();
            graph[w] = graph[w].Append(v).ToArray();
        }

        groups = new List<int[]>();

        for (int i = 1; i < N + 1; i++)
        {
            if (visited[i] == 0)
            {
                groups.Add(new int[] { costs[i - 1] });
                visited[i] = 1;
                dfs(i);
            }
        }

        int answer1 = 0;
        string answer2 = "";
        foreach (int[] group in groups)
        {
            answer1 += group.Min();
            if (answer1 > k)
            {
                answer2 = "Oh no";
                break;
            }
        }

        if (answer2 == "") Console.WriteLine(answer1);
        else Console.WriteLine(answer2);

    }

    static void dfs(int n)
    {
        foreach (int next in graph[n])
        {
            if (visited[next] == 0)
            {
                visited[next] = 1;
                groups[groups.Count - 1] = groups[groups.Count - 1].Append(costs[next - 1]).ToArray();
                dfs(next);
            }
        }
    }
}