[Java, 자바] 백준 11724번, 연결 요소의 개수

백준 11724번

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

난이도 : 실버2

---

문제내용

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

---

입력

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

---

출력

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

---

풀이방법

이번 문제도 역시 DFS를 통해 접근을 하였습니다 :)

뱡향 없는 그래프가 주어졌을 때는 2차원 배열에 [a][b], [b][a]를 모두 1로 처리해야 된다는 점 !

1부터 n까지 모두 확인이 진행되지만 방문된 값의 경우 이전 연결 요소에 포함 된다는 뜻이니까 방문하지 않은 값만 DFS 통해서 호출하였습니다. (값 증가시키는 부분 잊지 않기 !)

DFS에서 방문한 위치일 경우 return시키고 arr의 값이 1일 경우 다시 DFS를 호출시켜 마무리 하였습니다😀

 

---

코드

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

public class Main {
    static int n, m;
    static int[][] arr;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            arr[a][b] = 1;
            arr[b][a] = 1;
        }
        visit = new boolean[n + 1];
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (!visit[i]) {
                DFS(i);
                answer++;
            }
        }
        System.out.println(answer);
    }
    
    public static void DFS(int v) {
        if (visit[v]) return;
        else {
            visit[v] = true;
            for (int i = 1; i <= n; i++) {
                if (arr[v][i] == 1) DFS(i);

            }
        }
    }
}