[백준] 연결 요소의 개수 11724번 - Java

[백준] 연결 요소의 개수 11724번

나의 풀이

public class NumberOfConnectingElements {
    static int[][] graph = new int[1001][1001];
    static boolean[] visited = new boolean[1001];
    static int N, M;
    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());

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

            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        int answer = 0;
        for(int i = 1; i < N + 1; i++) {
            if(dfs(i)) {
                answer++;
            }
        }

        System.out.println(answer);
    }

    static boolean dfs(int idx) {
        if(visited[idx]) {
            return false;
        }

        visited[idx] = true;
        for(int i = 1; i < N + 1; i++) {
            if(graph[idx][i] == 1) {
                dfs(i);
            }
        }
        return true;
    }
}

• dfs에서 사용할 배열과 입력 값들을 클래스 변수로 선언한다.
• N, M 값을 입력받고, 입력되는 좌표의 graph 위치에 양방향으로 값을 1을 주어 연결시켜준다.
• N(노드의 개수) 만큼 돌면서 해당 dfs를 통해서 방문 여부를 확인한다.
• dfs는 만약 해당 노드의 인덱스가 방문한 적이 있다면, false를 리턴한다.
• 아니라면 해당 인덱스의 방문 여부를 true로 바꿔주고, 노드의 개수만큼 돌면서 해당 노드와 연결된 노드를 찾아 dfs를 돌려준다.