[백준/JAVA] 🥈 11724번 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입출력

 

 

 

풀이

💡 방법1  ➡️ 인접행렬 사용한 DFS

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

public class Main {
    static int N, M, count=0;
    static int[][] graph;
    static int[] ch;

    public static void main(String[] args) throws IOException {
        // 한 줄 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 한 줄 안에서 공백 기준으로 자르기
        StringTokenizer stk = new StringTokenizer(br.readLine());

        // 자른거 하나씩 저장
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());

        graph = new int[N+1][N+1];
        ch = new int[N+1];
        for(int i=0; i<M; i++){
            StringTokenizer str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            graph[a][b] = graph[b][a] = 1;
        }

        Main.Solution();
        System.out.println(count);
    }
    public static void Solution() {
        // 1번 노드부터 N번 노드까지 반복
        for (int i = 1; i < N+1; i++) {
            if(ch[i]==0) {
                count++;
                DFS(i);
            }
        }
    }
    public static void DFS(int v) {
        if(ch[v]==1) return;
        else {
            ch[v]=1;
            for(int i=0; i<N+1; i++) {
                if(graph[v][i]==1) {
                    DFS(i);
                }
            }
        }
    }
}

 

💡 방법2  ➡️ 인접리스트 사용한 BFS

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

public class Main {
    static int N, M, count=0;
    static List<List<Integer>> graph;
    static int[] ch;

    public static void main(String[] args) throws IOException {
        // 한 줄 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 한 줄 안에서 공백 기준으로 자르기
        StringTokenizer stk = new StringTokenizer(br.readLine());

        // 자른거 하나씩 저장
        N = Integer.parseInt(stk.nextToken()); //정점의 개수
        M = Integer.parseInt(stk.nextToken()); //간선의 개수

        graph = new LinkedList<>();
        for(int i=0;i<=N;i++){
            graph.add(new ArrayList<>());
        }

        for(int i=0; i<M; i++){
            StringTokenizer str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        int answer=0;
        ch = new int[N+1];
        for(int i=1;i<=N;i++){
            if(ch[i]==0){
                ch[i]=1;
                answer++;
                BFS(i);
            }
        }

        System.out.println(answer);
    }
    public static void BFS(int v){
        Queue<Integer> Q = new LinkedList<>();
        Q.add(v);
        while(!Q.isEmpty()) {
            int cv = Q.poll();
            for(int nv : graph.get(cv)) {
                if(ch[nv]==0) {
                    ch[nv]=1;
                    Q.add(nv);
                }
            }
        }
    }
}

 

 

느낀점

여러 사람의 알고리즘 코드를 보다보면 입력을 버퍼로 받는 코드가 대부분인데,

JY쓰에게 물어보니 나중에 입력 숫자가 많은 문제에서는 버퍼를 써야 에러가 안 난다고 한다.

그래서 이번 문제부터 바꿔 써봤는데 너무 어색하다.

 

 

 

아래는 첫 풀이었는데 테스트 케이스는 다 통과하지만 제출시 정답이 아니라고 뜬다.

단순히 if-return문 때문인지 궁금하다. 고쳐봐야징

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

public class ex11724 {
    static int N, M, count=0;
    static int[][] graph;
    static int[] ch;

    public static void main(String[] args) throws IOException {
        // 한 줄 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 한 줄 안에서 공백 기준으로 자르기
        StringTokenizer stk = new StringTokenizer(br.readLine());

        // 자른거 하나씩 저장
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());

        graph = new int[N+1][N+1];
        ch = new int[N+1];
        for(int i=0; i<M; i++){
            StringTokenizer str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            graph[a][b] = graph[b][a] = 1;
        }

        ex11724.Solution();
        System.out.println(count);
    }
    public static void Solution() {
        for (int i = 1; i < N+1; i++) {
            for (int j = 1; j < N+1; j++) {
                if(graph[i][j]==1 && ch[j]==0) {
                    ch[j]=1;
                    count++;
                    DFS(j);
                }
            }
        }
    }
    public static void DFS(int v) {
        for(int i=0; i<N+1; i++) {
            if(graph[v][i]==1 && ch[i]==0) {
                ch[i]=1;
                DFS(i);
            }
        }
    }
}

 

 

재영쓰가 예외 테케 찾아주고 보석쓰가 고쳐줬다..... 앞으로 막히면 절대 계속 매달려서 해결해봐야지

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

public class ex11724 {
    static int N, M, count=0;
    static int[][] graph;
    static int[] ch;

    public static void main(String[] args) throws IOException {
        // 한 줄 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 한 줄 안에서 공백 기준으로 자르기
        StringTokenizer stk = new StringTokenizer(br.readLine());

        // 자른거 하나씩 저장
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());

        graph = new int[N+1][N+1];
        ch = new int[N+1];
        for(int i=0; i<M; i++){
            StringTokenizer str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            graph[a][b] = graph[b][a] = 1;
        }

        ex11724.Solution();
        System.out.println(count);
    }
    public static void Solution() {
        for (int i = 1; i < N+1; i++) {
            if(ch[i]==0) {
                ch[i]=1;
                count++;
                DFS(i);
            }
        }
    }
    public static void DFS(int v) {
        for(int i=0; i<N+1; i++) {
            if(graph[v][i]==1 && ch[i]==0) {
                ch[i]=1;
                DFS(i);
            }
        }
    }
}