백준 11724번 연결 요소의 개수

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

public class Connected_Component {
    static int N,M;

    static int[][] map;
    static boolean[] visited;
    static int count = 0;
    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());
        M = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        visited = new boolean[N+1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            map[u][v] = 1;
            map[v][u] = 1;

        }

        for (int i = 1; i < N+1; i++) {
            if(!visited[i]) {
                dfs(i);
                count++;
            }
        }
        System.out.println(count);

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

    }
}

풀이 방법

📢이 풀이의 핵심은 간선에 해당하는 수를 좌표형태로 체크하는 것이다.

	map[u][v] = 1;
    map[v][u] = 1;

이렇게 해야 한 요소에 연결된 여러 간선을 표현할 수 있다.
1. 1번 요소부터 dfs 탐색을 시작하고, 연결된 요소를 따라 가며 전부 visited[] = true; 표시 해준다.
2. 더이상 탐색할 요소가 없다면 dfs를 끝내고 count를 증가시킨다.
3. 탐색하지 않은 요소에서부터 다시 탐색을 시작한다.

후기

좌표에 나타내야 한다는것을 모르면 생각해내기 어렵다. 난 저번에 한번 맞은적이 있어서 잘 기억해냈다.