BOJ) 연결 요소의 개수

연결 요소의 개수

11724번: 연결 요소의 개수

풀이

 

최근에 이 문제랑 거의 유사한 문제를 풀었던 것 같다. 그래서 비교적 빠르게 풀 수 있었다.

우선, 노드의 갯수 N은 1000 이하기 때문에, int형 배열을 이용해도 메모리 제한에 문제가 없다고 판단했다.

또한, 간선의 갯수 M은 N×(N-1)/2 즉, 최대의 경우 499,500이라는 숫자가 나오기 때문에 따로 저장을 하지 않고

입력을 받는 즉시 로직을 수행하도록 설정했다.

 

몇 개의 연결 요소가 있는지 구하는 문제였기 때문에, union-find를 이용해 풀었다.

간선을 모두 이어준 다음, parents를 탐색하면서 답의 갯수를 구해주었다.

이 때, 시간을 단축을 위해 visit 변수를 이용했다. (아마도 visit 변수가 없으면 시간 초과가 날 수도 있다. 안해봐서 잘 모르겠지만..)

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] parents;

    public static void main(String[] args) throws IOException{
        System.out.println(solution(new BufferedReader(new InputStreamReader(System.in))));
    }

    private static int solution(BufferedReader br) throws IOException {
        int answer=0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        inItParents(n);

        int m = Integer.parseInt(st.nextToken());
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            if(find(left) != find(right)) {
                union(left, right);
            }
        }
        br.close();

        boolean[] visit = new boolean[n+1];

        for(int i=1; i<=n; i++) {
            if(!visit[i]) {
                answer++;
                visit[i] = true;
                for(int j=1; j<=n; j++) {
                    if(i!=j && !visit[j]) {
                        if(find(i) == find(j)) {
                            visit[j] = true;
                        }
                    }
                }
            }
        }

        return answer;
    }

    private static void union(int left, int right) {
        left = find(left);
        right = find(right);

        if(left != right) {
            parents[right] = left;
        }
    }

    private static int find(int val) {
        if(val == parents[val]) {
            return val;
        }
        return parents[val] = find(parents[val]);
    }

    private static void inItParents(int n) {
        parents = new int[n+1];
        for(int i=1; i<=n; i++) {
            parents[i] = i;
        }
    }
}