구름톤 챌린지 4주 차 문제 17 학습 일기

https://goor.me/wDFSjuDNjzXTTqH4A

​

 

import java.io.*;
import java.util.*;
class Main {
	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());
		
		ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
		for(int i =0; i <= N; i++){
			arr.add(new ArrayList<Integer>());
		}
		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.get(a).add(b);
			arr.get(b).add(a);
		}
		Queue<Integer> q = new LinkedList<>();
		boolean []visited = new boolean[N+1];
		ArrayList<Node> ans = new ArrayList<>();
		
	
		for(int i = 0; i < N; i++){
			Double edge = 0.0;
			Node nd = new Node();
			if(arr.get(i).size() > 0 && !visited[i]){
				visited[i] = true;
				nd.nodeNum.add(i);
				for(int j = 0; j < arr.get(i).size(); j++){
					q.add(arr.get(i).get(j));
				}
				while (!q.isEmpty()){
					int nextNode = q.poll();
					edge++;
					if(!visited[nextNode]){
						visited[nextNode] = true;
						nd.nodeNum.add(nextNode);
						for(int j = 0; j < arr.get(nextNode).size(); j++){
							q.add(arr.get(nextNode).get(j));
						}
					}
				}
			nd.ans = edge / nd.nodeNum.size();
			ans.add(nd);
			}
		}
	
		for(int i = 0; i < ans.size(); i++)
			Collections.sort(ans.get(i).nodeNum);
		Collections.sort(ans, Node.customComparator);
		System.out.println(ans.get(0).ans);
		
		for(int i = 0; i <ans.get(0).nodeNum.size(); i++)
			System.out.print(ans.get(0).nodeNum.get(i) + " ");
	}
}


class Node{
    ArrayList<Integer> nodeNum = new ArrayList<>();
    Double ans;
	
    public static Comparator<Node> customComparator = new Comparator<Node>() {
        @Override
        public int compare(Node node1, Node node2) {
            // 1. ans가 가장 높은 것
            int ansComparison = Double.compare(node2.ans, node1.ans);
            if (ansComparison != 0) {
                return ansComparison;
            }

            // 2. ans가 같을 때 nodeNum의 인자갯수가 적은 것
            int numCountComparison = Integer.compare(node1.nodeNum.size(), node2.nodeNum.size());
            if (numCountComparison != 0) {
                return numCountComparison;
            }
					
            // 3. 2까지 같을 때는 nodeNum의 인자 중 가장 작은 인자가 있는 Node
            for (int i = 0; i < node1.nodeNum.size(); i++) {
                int numComparison = Integer.compare(node1.nodeNum.get(i), node2.nodeNum.get(i));
                if (numComparison != 0) {
                    return numComparison;
                }
            }

            return 0; // 모든 비교 기준이 같을 경우
        }
    };
}

 

쉽게 말하면 노드와 간선 수를 둘 다 구하면 된다.

근데 약간 꼼수 아닌 꼼수가 있다면, 실제는 양방향 간선으로 양 노드 간 간선 수를 하나로 세야 하지만,

그냥 각각 노드에서 간선의 수를 카운트 했기 때문에 2개로 치고 풀었다.

그래서 실제 밀도를 구하면 예시와는 다르지만 답은 맞는다.

그리고 밀도가 같을 때가 참 지저분한데, 그건 우리 형 gpt의 도움을 받아서 comparator의 compare 메소드를 오버라이드 해서 구현했다.

제시한 정답에서는 간선의 개수를 따로 세었는데. 난 그냥 탐색할 때 카운트 했다.