[Baekjoon] 16562_친구비

Gold IV

문제(출처: https://www.acmicpc.net/problem/16562)

---

<  친구비 >

 

문제 풀이 & 생각

 

bfs 탐색을 통해 친구의 친구 중에서 최소 비용을 구한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _16562_ { // 친구비
	static int f[], money;
	static ArrayList<HashSet<Integer>> arr;
	static boolean visited[];

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

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

		f = new int[n + 1];
		arr = new ArrayList<>();
		visited = new boolean[n + 1];
		st = new StringTokenizer(bf.readLine());
		for (int i = 1; i < n + 1; i++) {
			f[i] = Integer.parseInt(st.nextToken());
		}
		for (int i = 0; i < n + 1; i++) {
			arr.add(new HashSet<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			arr.get(v).add(w);
			arr.get(w).add(v);
		}

		int answer = 0;

		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				money = f[i];
				bfs(i);
				answer += money;
			}
		}

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

	}

	private static void bfs(int idx) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(idx);

		while (!queue.isEmpty()) {
			int num = queue.poll();
			for (int next : arr.get(num)) {
				if (!visited[next]) {
					visited[next] = true;
					if (money > f[next]) {
						money = f[next];
					}
					queue.add(next);
				}
			}
		}
	}
}

 

Main

- 학생 수 (n), 친구 관계 수 (m), 가지고 있는 돈(k) 입력

- f : 친구비
  arr : 친구 관계 저장
  visited: 방문 여부

- 학생 두 명(v, w) 입력 후 친구 관계(arr) 양방향으로 저장

- 친구 전체 탐색하며 아직 친구가 아니라면 친구 탐색 시작 (bfs 함수 호출)

- 모든 학생을 친구로 만들 수 있는 돈을 가지고 있다면 answer 출력, 돈이 부족하다면 "Oh no" 출력

 

bfs

- queue가 빌 때까지 반복 -> num의 인접 리스트 탐색하여 아직 방문하지 않은 곳이라면 방문 표시 / 현재 친구비 보다 친구의 친구비가 더 쌀 경우 친구비 교체 / queue에 추가 

---

---