[S2] 연결 요소의 개수 : Java : 11724 - DFS(무방향)

1. 문제

11724번: 연결 요소의 개수

 

 

2. 문제 풀이

해당 문제는 입력받은 간선의 정보대로 리스트(graph)에 담고 DFS 탐색을 진행하면 되는 문제이다.

결과는 연결 요소의 개수. 즉 노드의 집합이 몇개이냐 문제이다. 그러므로 DFS 탐색을 진행하다 해당 그래프의 탐색이 완료되면, 

Count를 1 더해주고 다른 노들 집합을 찾아 탐색을 진행한다.

2.1 그래프 구성

간선이 Nx(N-1)/2라면 무방향 그래프이다.

무방향 그래프는 서로를 자식으로 가진다. 즉 한쪽에만 추가해주면 안된다. 아래와 같이!

 for(int i = 0; i< M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[u].add(v);
            graph[v].add(u);
        }

단일 방향 그래프로 생각했을 때 과연 그래프를 끝을 어떻게 인식할 것인가 고민을 했었다. 한 번 방문 했던 노드가 다시 나올 수 있기 때문이었다. 하지만 무방향 그래프로 하니 탐색이 진행된 요소에 대해서는 `visited = false` 처리를 하면되어서 훨씬 풀이가 간단해졌다.

 

 

2.2  DFS 탐색

이때까지 `Iterator`를 이용하여 탐색을 했는데 코드가 길어져서 for문으로 대체하였다. 

 static void DFS(int index){
        visited[index] = true;
        for(int e : graph[index]){
            if(!visited[e])
                DFS(e);
        }
    }

 

2.3 전체 그래프 탐색

노드 집합의 개수를 알기 위해서는 모든 노드를 탐색해봐야 한다. 그러므로 i는 정점 N에 대해 모두 탐색을 하면서, 방문하지 않은 노드라면 DFS()를 호출한다. DFS()를 호출한다는 것은 새로운 노드 집합의 시작이라는 것이다. 그러므로 Count에 1을 더한다.

for(int i=1; i<=N; i++){
            if(visited[i]){
                continue;
            }
            DFS(i);
            count++;
        }

여기서 처음에 if 문에 자식의 개수가 0이 아닌지도 같이 체크를 했었다. 자식의 개수가 0인 노드는 탐색을 하지 않고 건너띄어도 된다고 생각했기 때문이다. 근데 '틀렸습니다'를 받았다. 왜 틀렸을까.. 아직 모르겠다.

 

전체 코드

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

public class BOJ_연결요소의_개수 {
    public static ArrayList<Integer> [] graph;
    public static boolean [] visited;
    public static int count = 0;

    public static void main(String [] args) throws Exception {

        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());

        graph = new ArrayList[N+1];
        visited = new boolean[N+1];

        for(int i=1; i<= N; i++){
            graph[i] = new ArrayList<>();
            visited[i] = false;
        }

        //간선 입력
        for(int i = 0; i< M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[u].add(v);
            graph[v].add(u);
        }

        for(int i=1; i<=N; i++){
            if(visited[i]){
                continue;
            }
            DFS(i);
            count++;
        }

        System.out.println(count);

    }
    static void DFS(int index){
        visited[index] = true;
        for(int e : graph[index]){
            if(!visited[e])
                DFS(e);
        }
    }

}