[구름톤 챌린지, Java] 17일차, 그래프의 밀집도(BFS)

 

문제 링크

구름LEVEL

 

---

접근 방법

이 문제에 핵심

1. N개의 컴퓨터 존재하며, 각 컴퓨터를 양방향 연결하는 M개의 회선이 존재합니다.

2. 같은 컴퓨터 쌍을 연결하는 회선은 최대 1개입니다.

3. 컴퓨터가 회선으로 연결되어 그룹을 컴포넌트라고 합니다.

4. 컴포넌트에는 밀도가 존재하며, 회선의 수 ÷ 컴퓨터의 수 입니다.

5. 밀도가 가장 높은 컴포넌트를 결과로 출력합니다.

6. 밀도가 같으면 문제의 조건에 맞게 결과를 반환합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 컴포넌트에 속하지 않는 컴퓨터를 기준으로 BFS을 진행하여 컴포넌트를 구성합니다.

 

3. 탐색이 종료되었을 때 조건에 맞는 컴포넌트의 컴퓨터들을 결과로 출력합니다.

 

 

구현

 

BFS을 진행할 때 각 회선이 연결된 컴퓨터는 같은 컴포넌트로 인식할 수 있습니다.

 

 

회선의 수 : 는 컴포넌트에 속한 회선의 수 ÷ 2

 

 

Why?

 

회선이 양방향이기 때문에 BFS을 진행할 때 회선 당 2번이 탐색되기 때문입니다.

 

컴포넌트에 속해있다는 것을 boolean[]로 저장합니다.

 

BFS을 종료하면 모든 컴퓨터는 컴포넌트에 속해있습니다.

 

컴포넌트의 밀도를 구할 때 점화식

 

회선의 수 ÷ 컴퓨터의 수

 

밀도의 값이 같을 때는 문제에 설명하는 조건에 맞게 설정합니다.

 

 

 

예제입력 진행과정을 살펴보시면 이해하시기 편하실 것입니다.

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 7

 

M : 6

2. 컴포넌트에 속하지 않는 컴퓨터를 기준으로 BFS을 진행하여 컴포넌트를 구성합니다.

 

컴포넌트에 속하지 않은 1번 컴퓨터 BFS 진행!

 

 

컴퓨터 1 : 회선 개수 : 2개

컴퓨터 3 : 회선 개수 : 3개

컴퓨터 5 : 회선 개수 : 1개

컴퓨터 7 : 회선 개수 : 2개

= 8개

 

컴퓨터 개수 : 4개

컴포넌트 회선 개수 : 회선 개수(8) ÷ 2 = 4개

 

밀도 : 4 ÷ 4 = 1

컴포넌트 A : {1, 3, 5, 7}

 

컴포넌트에 속하지 않은 2번 컴퓨터 BFS 진행!

 

컴퓨터 2 : 회선 개수 : 1개

컴퓨터 4 : 회선 개수 : 2개

컴퓨터 6 : 회선 개수 : 1개

= 4개

 

컴퓨터 개수 : 3개

컴포넌트 회선 개수 : 회선 개수(4) ÷ 2 = 2개

 

밀도 : 2 ÷ 3 = 0.666666

컴포넌트 B : {2, 4, 6 }

 

컴포넌트에 속한 {3, 4, 5, 6, 7}번 컴퓨터는 BFS 진행 X!

 

3. 탐색이 종료되었을 때 조건에 맞는 컴포넌트의 컴퓨터들을 결과로 출력합니다.

 

컴포넌트 A : { 1, 3, 5, 7 }, 밀도 : 1.0

 

컴포넌트 B : { 2, 4, 6 }, 밀도 : 0.66

 

컴포넌트 A의 컴퓨터들을 오름차순으로 결과를 출력합니다.

 

1 3 5 7을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• 컴포넌트에 속하지 않은 섬을 기준으로 connecting함수를 실행하여 연합을 맺습니다.
• 모든 컴포넌트를 만든 뒤 조건에 맞는 컴포넌트의 컴퓨터 정보를 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• connecting은 bfs를 통해서 회선으로 연결된 컴포넌트를 구성합니다.
• connecting은 컴포넌트의 밀도와 컴퓨터 개수를 기준으로 조건에 맞게 결과 컴포넌트와 비교를 진행합니다.

 

결과코드

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

class Main {
    //결과로 출력할 컴포넌트에 속한 컴퓨터 리스트
    static List<Integer> result = new ArrayList<>();
    //밀도 최대값 저장 변수
    static double max = -1;
    //회선 정보 저장 리스트
    static List<List<Integer>> conn = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        //회선 리스트 초기화
        for(int i=0;i<=N;i++){
            conn.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());
            conn.get(a).add(b);
            conn.get(b).add(a);
        }
        //컴포넌트 속해있는 유무 배열
        boolean[] isComponent = new boolean[N+1];
        //컴포넌트 속하지 않은 컴퓨터 기준 BFS을 통한 컴포넌트 생성
        for(int i=1;i<=N;i++){
            //이미 컴포넌트에 속하였을 때
            if(isComponent[i]){
                continue;
            }
            //BFS을 통한 컴포넌트 생성 진행
            connecting(i, isComponent);
        }
        //결과 컴포넌트 오름차순 정렬
        Collections.sort(result);
        //결과 컴포넌트 컴퓨터 값 StringBuilder 저장
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<result.size();i++){
            sb.append(result.get(i)).append(" ");
        }
        //StringBuilder에 저장된 컴퓨터 값 BufferedWriter 저장
        bw.write(sb.toString());
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 통한 컴포넌트화 진행
    static void connecting(int start, boolean[] isComponent){
        //BFS에 사용할 Queue
        Queue<Integer> q = new ArrayDeque<>();
        //현재 컴포넌트 컴퓨터 리스트
        List<Integer> computer = new ArrayList<>();
        //회선 개수
        int connCnt = 0;
        q.add(start);
        //시작값 Queue저장
        computer.add(start);
        //시작값 컴포넌트에 속하도록 설정
        isComponent[start] = true;
        //BFS탐색 시작
        while(!q.isEmpty()){
            int cur = q.poll();
            //현재 컴퓨터의 회선 개수 더하기
            connCnt += conn.get(cur).size();
            //회선으로 연결된 컴퓨터 탐색
            for(int nxt : conn.get(cur)){
                //컴포넌트에 이미 속한 컴퓨터일 때
                if(isComponent[nxt]){
                    continue;
                }
                isComponent[nxt] = true;
                //현재 컴포넌트에 해당 컴퓨터 추가!
                computer.add(nxt);
                q.add(nxt);
            }
        }
        //컴포넌트 회선의 수 구하기
        connCnt /= 2;
        //밀도 구하기
        double temp = (double)connCnt / computer.size();
        //조건에 맞게 컴포넌트 비교
        if(temp > max){		//조건 1.
            max = temp;
            result.clear();
            for(int val : computer){
                result.add(val);
            }
        }else if(temp == max){		//조건 2
            if(result.size() > computer.size()){
                result.clear();
                for(int val : computer){
                    result.add(val);
                }
            }else if(result.size() == computer.size()){		//조건 3
                Collections.sort(computer);
                Collections.sort(result);
                if(result.get(0) > computer.get(0)) {
                    result.clear();
                    for (int val : computer) {
                        result.add(val);
                    }
                }
            }
        }
    }
}

 

---

느낀 점

 

밀도를 구할 때 int ÷ int로 진행하면서, 밀도의 값이 제대로 구해지지 않는 상황을 고려하지 않고 왜 틀렸는지 디버깅을 진행하였습니다.

 

아직까지는 문제를 자세히 읽고 자료형을 선택할 때 매끄럽지 못하다고 판단됩니다.

 

문제를 빠르게 푸는 것도 중요하지만 정확하게 풀려고 노력을 해야겠다고 깨닫게 되었습니다.