[BOJ] 11724 연결 요소의 개수 - Java

문제

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

11724번: 연결 요소의 개수

---

풀이

• 2차원 배열에 입력되는 간선의 양 끝점을 입력 받기
• 루트 배열과 노드 배열은 1부터 시작하므로 크기를 +1로 초기화하고, 인덱스 1부터 입력 받기
•  초기 루트값을 자기 자신으로 초기화
• 두 노드의 루트 값을 비교할 때 작은 값을 기준으로 루트를 설정하기 때문에 인덱스 1번째 요소를 기준으로 오름차순 정렬 수행
• 1번부터 m번 반복을 돌며 노드 연결
• boolean으로 최종 루트 값 종류(연결 요소)  구하기

---

코드

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


public class Main {
    public static int n,m;
    public static int[] root; // 루트 노드 배열
    public static int findroot(int x){
        if(x == root[x]) return x;
        return root[x] = findroot(root[x]);
    }

    public static void connect(int x, int y){
        x = findroot(root[x]);
        y = findroot(root[y]);
        if(x < y) root[y] = x;
        else root[x] = y;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        root = new int[n+1];
        int[][] node = new int[m+1][2]; // 노드 입력받는 배열
        int cnt = 0; // 연결 요소 개수

        // 노드 입력 받기
        for(int i=1; i<=m; i++){
            st = new StringTokenizer(br.readLine());
            node[i][0] = Integer.parseInt(st.nextToken());
            node[i][1] = Integer.parseInt(st.nextToken());
        }
        // 루트 자기자신으로 초기화
        for(int i=1; i<=n; i++){
            root[i] =i;
        }

        // 배열 각부분 1번째 요소 기준 정렬 (오름차순)
        Arrays.sort(node, Comparator.comparingInt(o -> o[1]));

        // 노드 연결
        for(int i=1; i<=m; i++){
            if(findroot(node[i][0]) != findroot(node[i][1])){
                connect(node[i][0], node[i][1]);
            }
        }

        // root 로 연결 요소 개수 확인
        boolean[] check = new boolean[n+1];
        for (int i=1; i<=n; i++){
            if(!check[root[i]]){
                check[root[i]] = true;
                cnt++;
            }
        }
        System.out.println(cnt);

    }
}

 

---

문법

2차원 배열 정렬

• Comparator을 생성하는 메서드(comparingInt)와 메서드 참조 사용 방식
• o[0] 은 각 부분 배열의 0번째 요소를 가르키며, 그것을 기준으로 compare 한다는 의미
• 비교 기준이 같다면 입력 순서대로 저장
• 오름차순 정렬

Arrays.sort(arr, Comparator.comaparingInt(o -> o[0]));

 

---

리팩토링

리팩토링

• 불필요한 과정 줄이기
• 같은 로직이더라도 간결하게 코드 작성할 수 있도록 한 번 더 생각하기

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


public class Main {
    public static int[] root; // 루트 노드 배열
    public static int findRoot(int x){
        if(x == root[x]) return x;
        return root[x] = findRoot(root[x]);

    }

    public static void connect(int x, int y){
        x = findRoot(root[x]);
        y = findRoot(root[y]);
        if(x < y) root[y] = x;
        else root[x] = y;
    }

    public static void main(String[] args) throws IOException {
        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());
        root = new int[n+1];
        int cnt = 0; // 연결 요소 개수


        for (int i = 1; i <= n; i++) {
            root[i] = i;
        }

        // 노드 입력 받기
        for(int i=1; i<=m; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            connect(u, v);
        }

        // check 배열에서 findRoot()를 이용해 root 노드 갱신해서 정렬과정 줄임
        boolean[] check = new boolean[n+1];
        for(int i=1; i<=n; i++){
            if(!check[findRoot(i)]){
                check[findRoot(i)] = true;
                cnt++;
            }
        }
        System.out.println(cnt);
    }