백준 2610 회의준비

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

2610번: 회의준비

 

문제 잘못읽어서 겁나삽질 했음(역시 문제 잘읽는게 반이상이다)

 

서로 알고 있는 사람끼리 같은 그룹으로 묶어야하고(DFS)

그룹내에서 의사전달시간의 최대값이 최소인사람을 구해야한다(의사전달시간의 합이 최소라고 잘못읽어서 겁나삽질함)..

 

N이 100으로 매우 작으므로 graph 표현할때 인접행렬을 사용했고 (최대크기 101* 101)

그룹끼리 묶을때는 최소거리를 구할때는 플로이드 - 와샬 알고리즘 사용했다. (플로이드 와샬 사용할때 주의할점 k 가 가장바깥쪽에 있다. k는 삽입할 정점 번호)

평소에 잘 쓰지 않는 알고리즘이니 연습해두면 좋을듯 ~

 

package 백준;

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

public class 회의준비 {
	static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {

			bf = new BufferedReader(new InputStreamReader(System.in));

		}

		String next() {

			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();

		}

		int nextInt() {
			return Integer.parseInt(next());

		}

	}

	static int dist[][];
	static int color[];
	static int N;
	static int map[][];
	static int INF = 1000007;

	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		N = sc.nextInt();
		int M = sc.nextInt();
		color = new int[N + 1];
		map = new int[N + 1][N + 1]; // i to j 친구?

		com = new ArrayList[N + 1];
		int v[] = new int[N + 1];
		int cnt = 0;
		dist = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {

			com[i] = new ArrayList<Integer>();
			for (int j = 1; j <= N; j++) {
				dist[i][j] = INF;
			}
		}
		for (int i = 0; i < M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();

			dist[x][y] = 1;
			dist[y][x] = 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] == INF || dist[k][j] == INF || i == j)
						continue;

					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}

		boolean vv[] = new boolean[N + 1];
		for (int i = 1; i <= N; i++) {
			if (vv[i])
				continue;
			vv[i] = true;
			com[++cnt].add(i);
			for (int j = 1; j <= N; j++) {
				if (dist[i][j] != INF) {
					com[cnt].add(j);
					vv[j] = true;
				}
			}
		}
		
		System.out.println(cnt);
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		for (int i = 1; i <= cnt; i++) {
			pq.add(solve(i));
		}

		while (!pq.isEmpty()) {
			System.out.println(pq.poll());
		}

	}

	static ArrayList<Integer> com[];

	static int solve(int num) {

		ArrayList<Integer> group = com[num];

		int min_sum = 100007;

		int psum = 0;
		int answer = group.get(0);
		for (int i = 0; i < group.size(); i++) {
			psum = 0;
			int x = group.get(i);

			for (int j = 0; j < group.size(); j++) {
				int y = group.get(j);
				if (dist[x][y] == INF)
					continue;
				if (psum < dist[x][y])
					psum = dist[x][y];
			}
			if (min_sum > psum) {
				min_sum = psum;
				answer = x;
			}
		}
		return answer;

	}

}