BOJ_11724 연결 요소의 개수 풀이 [Java] (S2)

문제 설명

 

풀이

연결되어있는 선들의 연결요소를 구하는 문제였다.

생각해보면, 모든 선을 체크해보면서 같은 연결요소인지 체크를 해봐야하니 DFS나 BFS가 적합하다고 판단했다.

 

좀 더 생각해보면 DFS를 통해 연결요소를 모두 찾고 visit을 체크 해준 다음, 나머지 연결 안된 요소들을 또다시 DFS로 돌리면 된다는 것을 깨달을 수 있다.

 

그래서 DFS로 풀기 시작하는데, ArrayList안에 ArrayList를 넣는 형식으로 풀이하였다

ArrayList에 정점의 갯수만큼 ArrayList를 만들어주었다.

그리고 양방향으로 선을 모두 입력시켜주었다.

마지막으로 가장 바깥의 ArrayList를 돌면서 체크가 안되어있는 정점을 DFS로 돌린다. (+ 카운트도 추가해줌)

 

DFS에서는 정점과 연결된 정점들에 대한 For문을 돌리면서 다시 DFS를 돌리면 완성!!

 

중간에 visit을 체크해주면서 dfs를 돌리고 answer를 추가해주는게 핵심이다!!

 

깨닫게 된 점

• DFS 내부에서 visit = true를 설정해주어야 한다.
• visit를 1차원 배열로만 사용해도 되는데 너무 힘들게 생각했다.
• 점마다 visit안한 정점을 DFS로 돌리고, 연결된 것들을 함수내에서 다시 for문으로 실행시키면 된다.

 

코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static ArrayList<ArrayList<Integer>> dots;
    static int count;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dots = new ArrayList<>();

        for(int i=1; i< N+2; i++){
            dots.add(new ArrayList<Integer>());
        }

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

            dots.get(a).add(b);
            dots.get(b).add(a);
        }
        visit = new boolean[N+1];
        count = 0;

        for(int i=1; i < N+1; i++){
            if(!visit[i]){ //아직 체크가 안됐을 경우
                dfs(i);
                count++;
            }
        }
        System.out.println(count);
    }

    private static void dfs(int x) {
        if (visit[x]) return;
        else{
            visit[x] = true;
            for(int i : dots.get(x)){
                if(!visit[i]){
                    dfs(i);
                }
            }
        }
    }
}

 

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

11724번: 연결 요소의 개수