유형 : Union-Find + 플로이드 워셜 / BFS + 플로이드 워셜
문제에서 요구하는 것이 무엇인지 정확히 이해해야 한다.
나도 처음에는 간선이 가장 적은 사람을 대표자로 뽑으면 되는거 아냐? 하고 BFS로 풀이했다가 21%에서 틀렸습니다를 받았다.
9
8
1 2
2 3
3 4
4 5
4 6
4 7
4 8
4 9
1
3
처음엔 왜 틀렸는지도 몰랐다가 이 예제를 접하고 이해가 됐다.
내가 생각한대로라면 간선이 가장 많은 4번이 대표자가 되어야 하지만 답은 3이다.
왜일까? 문제에서는 위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 정하는 프로그램을 작성하라고 했다.
이 표와 같이 서로 알고 있는 사람들은 1의 dist를 갖는다.
(나머지는 생략했지만 Integer.MAX_VALUE의 값을 갖는다고 가정했다.)
이때 대표자가 4면 의사전달시간의 최댓값이 1번과의 의사전달시간으로 3이 된다.
반면 대표자가 3이면 의사전달시간의 최댓값은 2가 된다.
💡 아이디어
따라서 이 문제에서는 Union-Find와 플로이드 워셜 모두를 사용해야 한다.
-
Union-Find를 사용해서 서로 아는 사람들끼리 union 해준다.
-
플로이드 워셜을 사용해서 각 사람간의 거리를 계산해준다.
-
같은 부모를 가진 사람, 즉 같은 그룹인 사람들을 탐색한다. 이때 의사전달시간의 최댓값을 구하고 그 값이 최소인 대표자를 선발한다.
(의사전달시간이 같다면 인덱스가 작은 대표자를 선발해주어도 되고 안해주어도 된다.) -
그룹의 개수와 대표자를 출력한다.
개인적으로 Union-Find와 플로이드 워셜을 익히기 좋은 문제 같다.
+다른 풀이) BFS로 그룹 수를 count한 후 플로이드 워셜로 최댓값이 가장 적은 리더를 구해도 된다.
풀이
Union-Find + 플로이드 워셜 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/**
* 백준 2610번 회의준비
* - Union-Find + 플로이드 워셜
*/
public class Main {
public static int N;
public static int[] parent;
public static int[][] dist;
public static boolean[] visited;
public static PriorityQueue<Integer> pq;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
parent = new int[N + 1];
dist = new int[N + 1][N + 1];
pq = new PriorityQueue<>();
for (int i = 1; i <= N; i++) parent[i] = i;
for (int i = 1; i <= N; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
for (int i = 1; i <= N; i++) dist[i][i] = 0;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
union(a, b);
dist[a][b] = dist[b][a] = 1;
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
visited = new boolean[N + 1];
int groupCount = 0;
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
int leader = findLeader(i);
pq.add(leader);
groupCount++;
}
}
System.out.println(groupCount);
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
public static int find(int n) {
if (parent[n] == n) return n;
return parent[n] = find(parent[n]);
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) parent[b] = find(parent[a]);
}
public static int findLeader(int s) {
int root = find(s);
visited[s] = true;
List<Integer> group = new ArrayList<>();
// 같은 부모를 가진 사람 = 같은 그룹인 사람
for (int i = 1; i <= N; i++) {
if (find(i) == root) {
group.add(i);
visited[i] = true;
}
}
int minCommunicationTime = Integer.MAX_VALUE;
int leader = -1;
for (int node : group) {
int maxDist = 0;
for (int other : group) {
maxDist = Math.max(maxDist, dist[node][other]);
}
if (maxDist < minCommunicationTime) {
minCommunicationTime = maxDist;
leader = node;
} else if (maxDist == minCommunicationTime && node < leader) {
leader = node;
}
}
return leader;
}
}
BFS + 플로이드 워셜 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static List<List<Integer>> list;
public static boolean[] visited;
public static int count = 0, N;
public static PriorityQueue<Integer> pq;
public static int[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
visited = new boolean[N + 1];
list = new ArrayList<>();
pq = new PriorityQueue<>();
arr = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i != j) arr[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i <= N; i++) list.add(new ArrayList<>());
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[a][b] = arr[b][a] = 1;
list.get(a).add(b);
list.get(b).add(a);
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (arr[i][k] != Integer.MAX_VALUE && arr[k][j] != Integer.MAX_VALUE) arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= N; i++) {
if (!visited[i]) bfs(i);
}
sb.append(count + "\n");
while (!pq.isEmpty()) sb.append(pq.poll() + "\n");
System.out.println(sb);
}
public static void bfs(int n) {
count++;
List<Integer> group = new ArrayList<>();
group.add(n);
Queue<Integer> queue = new ArrayDeque<>();
queue.add(n);
visited[n] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int i = 0; i < list.get(cur).size(); i++) {
int next = list.get(cur).get(i);
if (!visited[next]) {
queue.add(next);
visited[next] = true;
group.add(next);
}
}
}
int min = Integer.MAX_VALUE;
int representative = -1;
for (int person : group) {
int maxDistance = 0;
for (int other : group) {
if (person == other) continue;
maxDistance = Math.max(maxDistance, arr[person][other]);
}
if (maxDistance < min) {
min = maxDistance;
representative = person;
}
}
pq.add(representative);
}
}
백엔드 개발자 연습생