[코딩테스트 챌린지] 백준 11724 연결 요소의 개수 (java)

문제

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

 

문제 탐색하기

1. 연결 요소의 개수란?

연결 요소란 그래프 내에서 연결되어 있는 정점들을 한 그룹으로 묶는 것을 말합니다.

한 정점에서 시작해서 연결된 모든 정점들을 순차적으로 탐색한 후에 한 그룹으로 묶는 과정은 DFS로 탐색할 수 있습니다.

 

N의 길이를 가진 배열을 선언하여 연결요소로 탐색된 곳을 true로 표기하는 boolean 배열을 선언합니다.

입력받은 input 값을 체크할 2차원 배열도 선언합니다. 각 노드 쌍 (a,b)가 입력되었다면 양방향 간선이므로 arr[a][b], arr[b][a] 를 1로 선언합니다.

 

2. DFS 를 통해 연결 요소 찾기

1번 노드부터 n번 노드까지 visit[] 배열을 확인하고, 방문하지 않은 노드를 발견할 때마다 dfs() 메소드를 호출합니다.

dfs() 메소드는 현재 노드와 연결되어있는 모든 노드를 재귀적으로 방문하고, 더 이상 연결되어있는 노드가 없으면 종료합니다.

한번 dfs() 사이클이 끝나면 새로운 연결 요소를 찾은 것이므로 카운트 변수를 선언하여 +1 처리를 해줍니다.

 

코드 설계하기

1. 변수 선언
   • N : 노드의 수
   • M : 간선의 수
   • arr[][] : 인접 행렬, 그래프를 표현하는 2차원 배열
   • visit[] : 노드 방문 여부 체크 배열
   • result : 연결 요소 개수 저장 변수
2. 입력 노드 쌍은 양방향 간선이므로 arr[a][b], arr[b][a] = 1
3. 방문하지 않은 노드일 경우 dfs() 메소드 호출하여 재귀적으로 인접 노드 탐색
4. dfs() 호출 후 더 이상 방문할 수 있는 노드가 없는 경우 1개의 연결 요소 탐색을 완료하고 result +1 처리
5. 결과 출력

 

정답 코드

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

public class ConnectedComponent {

    static int N, M;
    static int[][] arr; // 인접 행렬
    static boolean[] visit; // 방문 여부 체크 배열

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());

        N = Integer.parseInt(st.nextToken()); // 정점 개수
        M = Integer.parseInt(st.nextToken()); // 간선 개수

        arr = new int[N+1][N+1];
        visit = new boolean[N+1];

        for(int i=0; i<M; i++){
            st = new StringTokenizer(reader.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = arr[b][a] = 1;
        }

        int result = 0;
        for(int i=1; i<N+1; i++){
            // 방문한 적이 없을 경우 dfs 실행
            if(!visit[i]){
                dfs(i);
                result++;
            }
        }

        System.out.println(result);
    }

    public static void dfs(int number){
        visit[number] = true;
        for(int i=1; i<N+1; i++){
            if(!visit[i] && arr[number][i] == 1){
                dfs(i);
            }
        }
    }
}