[백준/BOJ] 2606 바이러스 - JAVA - 실버3

[백준/BOJ] 2606 바이러스 - JAVA - 실버3

문제

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

문제 분석

조건

• 네트워크로 연결된 컴퓨터들 사이에서 1번 컴퓨터와 연결된 컴퓨터의 수를 구하는 문제이다.

풀이방법

• 많은 문제를 BFS를 활용하며 해결하므로 DFS를 통해 문제 해결을 해보았다.
• DFS를 구현하여 문제를 해결할 수 있는데 1번 노드를 제외한 연결된 노드의 수를 출력하므로 마지막에 `-1`를 해주었다.

코드

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

public class Main {
    static boolean[][] graph;
    static boolean[] visited;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        graph = new boolean[N + 1][N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a][b] = true;
            graph[b][a] = true;
        }
        visited[1] = true;
        System.out.println(dfs(1) - 1);
    }

    private static int dfs(int now) {
        int count = 0;
        for (int next = 1; next <= N; next++) {
            if (now == next || visited[next]) { // 방문체크
                continue;
            }
            if (graph[now][next]) {
                visited[next] = true;
                count += dfs(next);
            }
        }
        return count + 1;
    }
}

결과