Java | 백준 11724 연결 요소의 개수

백준 11724 연결 요소의 개수 문제에 대한 글입니다.

백준 11724 연결 요소의 개수

백준 11724 연결 요소의 개수

문제

문제는 아래 링크에서 확인할 수 있다.

11724번: 연결 요소의 개수

풀이

재귀 호출을 이용한 DFS

2차원 배열을 이용해서 연결 정보를 입력받느다. 그 다음 재귀 호출을 이용해 DFS를 수행한다.

특징

정보는 2차원 배열에 담았지만, 방문 이력은 1차원 배열에 담는다. 연결 정보 상관없이, 연결 돼 있는 노드에 일단 방문했는지 여부만 체크하면 되기 때문에, 방문 이력은 1차원으로 충분하다.

전체코드

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

public class baekjoon11724 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int node, edge;
    static boolean[][] map;
    static boolean[] visited;

    static void input() throws IOException{
        st = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());
        map = new boolean[node+1][node+1];
        visited = new boolean[node+1];


        for(int i=0; i<edge; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = true;
            map[b][a] = true;
        }
    }

    static int execute(){
        int result = 0;

        for(int i=1; i<node+1; i++){
            if(!visited[i]){
                dfs(i);
                result++;
            }
        }

        return result;
    }

    static void dfs(int x){
        if(!visited[x]) {
            visited[x] = true;
            for(int i=1; i<node+1; i++){
                if(map[x][i]){
                    dfs(i);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(execute());
    }
}

배운 점

연결 정보를 2차원 배열에 담고, 방문 이력은 1차원 배열로 체크하는 방법을 알게 되었다. 차원을 줄이는 개념이기 때문에 다른 부분에서도 이용할 수 있을 것이라고 생각이 든다.