[Java] 백준_연결 요소의 개수_11724

문제

분석

방향 없는 그래프 + DFS 문제. 그래프를 코드로 표현할 때에는 인접행렬과 인접리스트로 표현할 수 있다. 노드 갯수가 1,000개 이상일 경우에는 인접리스트로 그래프를 표현하는게 좋다. 인접리스트의 경우 연결된 정보만을 리스트에 추가하지만 인접행렬의 경우 연결되지 않은 정보(0) 또한 탐색하게 되기때문이다.

 

우선은 기본적으로 체크배열, 인접리스트를 초기화 한다. 그리고 모든 노드들을 순차 탐색하면서 연결되있는 노드를 DFS한다. 그리고 방문한 노드는 체크를 해줌으로써 다시 방문하지 않게 만든다.

소스코드

package Doit알고리즘;

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

/*
 * https://www.acmicpc.net/problem/11724
 * - 데이터크기: 1,000
 * - 제한시간: 3초
 * 방향 없는 그래프 + DFS 문제. 노드의 갯수가 최대 1,000개이므로 인접행렬보다는 인접리스트를 사용하는게 좋다.
 * */
public class 연결요소의갯수_023 {

    static int n;
    static int e;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] checked;
    static int answer = 0;

    public static void dfs(int node) {
        for (Integer v : graph.get(node)) {
            if (!checked[v]) {
                checked[v] = true;
                dfs(v);
            }
        }
    }

    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());
        e = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        checked = new boolean[n + 1];

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            graph.get(node1).add(node2);
            graph.get(node2).add(node1);
        }

        for (int i = 1; i <= n; i++) {
            if (!checked[i]) {
                answer++;
                checked[i] = true;
                dfs(i);
            }
        }
        System.out.println(answer);
    }
}

결과