[백준] 16562번 '친구비' - Java

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 564508KB | 시간 1000ms | 코드 길이 2304B

import java.io.*;
import java.util.*;

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int[] friends;
	private static boolean[] visited;
	private static int min;
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int K = k;
		
		int[][] node = new int[n][n];
		
		StringTokenizer st_k = new StringTokenizer(bf.readLine());
		friends = new int[n];
		for(int i = 0 ; i < n ; i++) {
			friends[i] = Integer.parseInt(st_k.nextToken());
		}
		
		for(int i = 0 ; i < m ; i++) {
			StringTokenizer st_c = new StringTokenizer(bf.readLine());
			int x = Integer.parseInt(st_c.nextToken()) - 1;
			int y = Integer.parseInt(st_c.nextToken()) - 1;
			node[x][y] = 1;
			node[y][x] = 1;
		}
		
		visited = new boolean[n];
		
		PriorityQueue<Integer> graph = new PriorityQueue<>();
//		Stack<Integer> graph = new Stack<>();
		boolean flag = true;
		
		for(int i = 0 ; i < n ; i++) {
			if(!visited[i]) {
				min = 10000000;
				bfs(graph, node, i);
//				dfs(graph, node, i);
				k -= min;
			}
			if(k < 0) {
				flag = false;
				break;
			}
		}
		if(!flag) {
			bw.write("Oh no");
		} else {
			bw.write(Integer.toString(K - k));
		}
		
		bf.close();
		bw.flush();
		bw.close();	
	}
	private static void bfs(PriorityQueue<Integer> graph, int[][] node, int n) {
		visited[n] = true;
		min = Math.min(friends[n], min);
		graph.poll();
		for(int i = 0 ; i < node.length ; i++) {
			if(!visited[i] && node[n][i] == 1) {
				graph.add(i);
				bfs(graph, node, i);
			}
		}
	}
	
	private static void dfs(Stack<Integer> graph, int[][] node, int n) {
		visited[n] = true;
		min = Math.min(friends[n], min);
		graph.push(n);
		for(int i = 0 ; i < node.length ; i++) {
			if(!visited[i] && node[n][i] == 1) {
				dfs(graph, node, i);
			} else if(visited[i] && node[n][i] == 1 && graph.size() > 0) {
				graph.pop();
			}
		}
	}
}

friends 배열에는 친구비가 들어갑니다. node 배열에는 각 노드에 해당하는 간선이 들어가고, 큐의 graph는 bfs에, 스택의 graph는 dfs에 활용됩니다.

bfs 함수를 이용하려면 위 코드를 그대로 실행시키면 되고, dfs 함수를 이용하려면 위 코드에서 주석 된 부분을 다시 실행시키고 큐와 bfs 함수 사용 부분을 주석시키면 됩니다.

https://cuckoobird.tistory.com/96 함수는 이 글의 함수와 같게 짜였지만, 달라진 점이라면 탐색마다 min의 변수에 friends배열 중 가장 작은 값을 저장해둔 점입니다.

---

후기

전에 함수로 구현할때 나중에 또 그래프 탐색 풀면 그대로 복붙하려고 하기도 했는데 활용할 수 있어서 좋네요..^_^ 

분리집합으로 풀 수도 있는 것 같은데 아직 무슨말인지 이해가 안 돼서 다음에 쉬운문제로 분리집합 한번 풀어보겠습니다.