백준 11724번 연결 요소의 개수

문제 링크 : https://www.acmicpc.net/problem/11724

1. 입력받은 정점의 갯수 n으로 n x n 크기의 배열을 만들어 간선연결정보를 입력받아 저장하였다.

무방향 그래프이므로 좌표의 x, y 순서를 바꿔주면 두번 표시해주었다.

2. n크기의 1차원배열 visitied를 만들어 배열을 탐색하며 방문하지않은 정점을 대상으로 dfs를 수행하고 이경우 int형 변수 count값을 증가시켜주었다

3. 반복문이 종료된 후 count 값을 출력하였다.

dfs함수는 현재정점 값을 입력받아 간선연결정보를 저장한 배열을 보며 현재 정점과 연결되어있고 방문하지않은 정점이 있는경우 그 정점값을 넘겨주며 dfs를 재귀호출하도록 하였다.

아래는 소스코드이다.

import java.util.Scanner;
public class Main {
    
    static int n;
    static int[][] gansun;
    static boolean[] visited;
    
    public static void main(String[] args) {
        
        int m, count=0;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        gansun = new int[n+1][n+1];
        visited = new boolean[n+1];
        
        for(int i=0; i<m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            gansun[a][b] = 1;
            gansun[b][a] = 1;
        }
        
        for(int i=1; i<=n; i++) {
            if(visited[i] == false) {
                dfs(i);
                count++;
            }
        }
        
        System.out.println(count);
    }
    
    static public void dfs(int point) {
        visited[point] = true;
        for(int i=1; i<=n; i++) {
            if(gansun[point][i]==1 && visited[i]==false) {
                dfs(i);
            }
        }
    }
}