구름톤 챌린지 17일차

문제

https://level.goorm.io/exam/195699/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98-%EB%B0%80%EC%A7%91%EB%8F%84/quiz/1

구름LEVEL

 

풀이

이 문제도 전 문제와 같이 그래프 문제이다. 그래프에서의 완전탐색이므로 BFS를 이용하여 문제를 풀었다.

문제 내에서 구해야 하는 것은 3가지이다.

1. 그래프 컴포넌트 리스트

2. 그래프 컴포넌트 사이즈

3. 그래프 컴포넌트 사이의 회선 개수

 

1과 2 같은 경우는 여태까지 bfs를 풀었던 것처럼 구하면 된다.

다만 3번 같은 경우는 다음과 같이 구한다. 

bfs를 이용하여 그래프 컴포넌트 리스트를 구하고 각 요소들마다 연결된 노드들에 대해 요소가 노드보다 작을때만 edge의 수를 1씩 증가시키면 된다.

int edge = 0;
for(int i : list){
    for(int to : arr[i]){
        if(i < to)
            edge++;
    }
}

 

문제는 bfs 함수에서 1,2,3에서 구한 컴포넌트 리스트와 밀도를 같이 리턴해야 된다는 것이다.

따라서, 이를 Pair라는 class를 하나 만들어 주어 return을 해줘야 한다. 또한, Pair에 밀도를 mapping 할때 double로 형변환을 해줘야 한다. 

 

출력은 다음과 같은 조건을 만족해야 출력한다.

1. 가장 밀도가 높은컴포넌트를 출력한다.

2. 1을 만족하는 컴포넌트가 여러 개라면, 컴포넌트를 구성하는컴퓨터의 수가 가장 작은컴포넌트를 출력한다.

3. 2를 만족하는 컴포넌트가 여러 개라면,더 작은 번호를 가진 컴퓨터가 있는 컴포넌트를 출력한다.

 

이 3가지에 대해 if-else문을 작성하면 된다.

 

코드

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

class Main {
	static boolean visited [];
	static List<Integer> arr [];
	
	public static void main(String[] args) throws Exception {
		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());
		
		arr = new LinkedList [n+1];

		visited = new boolean [n+1];
		
		for(int i=1;i<=n;i++){
			arr[i] = new LinkedList<>();
		}
		
		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].add(b);
			arr[b].add(a);
		}
		
		double max = 0;
		List<Integer> result = new ArrayList<>();
		
		for(int i=1;i<=n;i++){
			 if(!visited[i]){
				 Pair pair = bfs(i);
				 double density = pair.value;
				 List<Integer> list = pair.list;
				 
				 
				 if(density > max){
					 max = density;
					 result = list;
				 }
				 else if(density == max){
					 if(result.size() > list.size()){
						 max = density;
						 result = list;
					 }
					 else if(result.size() == list.size()){
						 if(result.get(0) > list.get(0)){
							 max = density;
							 result = list;
						 }
					 }
				 }
			 }
			
		}
		
		Collections.sort(result);
		for(int i:result){
			System.out.print(i+" ");
		}
	}
	
	static Pair bfs(int start){
		List<Integer> list = new ArrayList<>();
		Queue<Integer> que = new LinkedList<>();
		list.add(start);
		que.add(start);
		visited[start] = true;
		
		while(!que.isEmpty()){
			int pos = que.poll();
			
			for(int i=0;i<arr[pos].size();i++){
				int next = arr[pos].get(i);
				if(visited[next]) continue;
				que.add(next);
				visited[next] = true;
				list.add(next);
			}
		}
		
		int edge = 0;
		for(int i : list){
			for(int to : arr[i]){
				if(i < to)
					edge++;
			}
		}

		
		return new Pair((double)edge/list.size(), list);
		
		
	}
	
	static class Pair {
		double value;
		List<Integer> list;
		
		public Pair (double value, List<Integer> list){
			this.value = value;
			this.list = list;
		}
	}
}