문제

실버2 난이도의 그래프탐색 문제이다.

풀이

정점과 간선의 정보들을 이차원 배열에 저장한다.
연결되어 있는 정점의 경우 배열의 값을 1로 저장한다.
visited 배열을 boolean 타입으로 선언 후 초기화한다.
정점의 개수 N만큼 visited 배열에서 반복문을 돌며 방문하지 않았을 경우 dfs를 실행하고 result에 1을 더해준다.

간단한 그래프 탐색 문제였다. DFS, BFS 어떤 방식으로 풀어도 무방할 것 같다.

package BOJ;

import java.io.*;
import java.util.*;

public class sol11724 {

    public static boolean[] visited;
    public static int[][] map;
    public static int n;
    public static int m;
    public static int u;
    public static int v;
    public static int result;


    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());
        result = 0;

        map = new int[n + 1][n + 1];
        visited = new boolean[n + 1];


        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            map[u][v] = 1;
            map[v][u] = 1;
        }

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

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

}