백준 [자바 java] 16562번 : 친구비

문제설명

준석이는 친구를 사귀기 위해서는 친구비를 내야한다.

이 때 친구비를 내서 사귄 친구의 친구는 그냥 사귈 수 있다. 

모든 친구를 사귀기 위한 친구비의 최소비용은?

 

풀이

dfs로 풀었다. 한 무리를 탐색할 때마다 그 무리 중 친구비가 가장 적은 비용을 구한다.

그 친구비의 합이 준석이가 가지고 있는 비용보다 작으면 Oh no를 출력한다.

package org.example;
import java.util.*;
import java.io.*;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    int[] mon = new int[n+1];
    int[] vis = new int[n+1];

    st = new StringTokenizer(br.readLine());
    for(int i = 1;i<=n;i++){
      mon[i] = Integer.parseInt(st.nextToken());
    }

    ArrayList<ArrayList<Integer>> list = new ArrayList<>();

    for(int i = 0;i<=n;i++){
      list.add(new ArrayList<>());
    }

    for(int i = 1;i<=m;i++){
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      list.get(a).add(b);
      list.get(b).add(a);
    }
    int ans = 0;

    for(int i = 1;i<=n;i++){
      Stack<Integer> stack = new Stack<>();
      int nowMon = 10000000;
      if(vis[i] == 0){
        vis[i] = 1;
        stack.push(i);
        while(!stack.isEmpty()){
          int now = stack.pop();
          vis[now] = 1;
          if(nowMon > mon[now]){
            nowMon = mon[now];
          }
          for(int j = 0;j<list.get(now).size();j++){
            if(vis[list.get(now).get(j)] == 0){
              stack.push(list.get(now).get(j));
            }
          }
        }
        ans += nowMon;
      }
    }

    if(k < ans){
      System.out.println("Oh no");
    }
    else{
      System.out.println(ans);
    }
  }
}

 

한번에 성공!

 

https://www.acmicpc.net/problem/16562