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

🔺 문제

11724번: 연결 요소의 개수

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static boolean visited[];
    static ArrayList<Integer>[] A;    // 2차원 ArrayList 배열
    
    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());   // 간선
        
        // 방문 기록 저장 배열
        visited = new boolean[n+1];
        
        // 그래프 데이터 저장 인접 리스트
        A = new ArrayList[n+1];   
        
        // A 인접 리스트의 각 ArrayList 초기화하기
        for(int i=1 ; i < n+1 ; i++) {
            A[i] = new ArrayList<>();
        }
        
        // A 인접 리스트에 그래프 데이터 저장하기
        for(int i = 0 ; i < m ; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end   = Integer.parseInt(st.nextToken());
            
            // 양방향 다 원소 추가해주기
            A[start].add(end);
            A[end].add(start);
        }
        
        int count = 0;
        
        // 📍 n의 개수만큼 반복 (0번은 안 씀!)
        for(int i = 1 ; i <= n ; i++) {
            if(!visited[i]) {
                count++;
                DFS(i);
            }
        }
        System.out.println(count);
    }
    
    // DFS 구현
    private static void DFS(int v) {
        // 종료 조건 : 현재 노드가 방문 노드인 경우
        if(visited[v]) return;
        
        visited[v] = true;
 
        // 현재 연결 노드 중 방문하지 않은 노드로 DFS 실행
        for(int i : A[v]) {
            if(!visited[i]) {
                DFS(i); // 재귀함수
            }
        }
    }
}

♦ DFS 수행 횟수 = 연결 요소 갯수

∙ 연결만 되어있고 방향성은 상관 X.

 

♦ 방문 기록 저장 배열 (boolean[]) & 그래프 데이터 저장할 인접 리스트(ArrayList<Integer>) 필요

∙ 방문 기록 저장 배열에서 0번은 안 씀!

 

♦ 재귀 함수 사용

 

🔺 다른 풀이들

https://www.acmicpc.net/source/57102783

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int n, m;
    static int[][] arr;          // 인접행렬
    static boolean[] visited;    // 방문체크
 
    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()); // 간선
        
        arr = new int[n+1][n+1];
        visited = new boolean[n+1];
        
        // 인접행렬 입력
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int f = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            arr[f][s] = arr[s][f] = 1;
        }
        
        // 연결 요소 개수
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs(i);
                cnt++;
            }
        }
        System.out.println(cnt);
    }
 
    public static void dfs(int st){
        if (visited[st]) return;
        visited[st] = true;
        
        for (int i = 1; i <= n; i++) {
            if (arr[st][i] == 1) {
                dfs(i);
            }
        }
    }
}

[백준 알고리즘] 백준 11724번 연결 요소의 개수 자바(Java)

인접 행렬을 2차원 배열로 선언하고 푸셨다.

 

---

1회독	2회독	3회독	4회독	5회독
V	6/15	9.4

 

 

(+ 3회독 9.4)

BFS로 풀어보았다.

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, cnt;
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    
    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());
        
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        visited = new boolean[N + 1];
        
        while(M -- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
        
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());     
            
            A[u].add(v);
            A[v].add(u);
        }
        
        for(int i = 1 ; i <= N ; i++) {
            if(!visited[i]) {
                bfs(i);
                cnt++;
            }
        }
 
        System.out.println(cnt);
    }
    
    private static void bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(int next : A[now]) {
                if(!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }
}

 

---

(참고)

 

- BufferedReader, StringTokenizer 사용법

[Java] 빠른 입출력을 위한 BufferedReader, BufferedWriter, StringTokenizer, StringBuilder

BufferedReader와 BufferedWriter의 사용법 (JAVA)

 

 

- int 배열의 ArrayList

Java에서 int 배열의 ArrayList 가져오기

 

 

- 2차원 ArrayList

Java: ArrayList 2차원 배열 생성