[백준] 2606번: 바이러스 - JAVA

문제 링크

BOJ 2606번: 바이러스

2606번: 바이러스

 

풀이 과정

바이러스는 연결된 네트워크를 통해 모두 전파되므로 연결되어 있는 모든 경로를 탐색하면 되는 문제이다.

DFS와 BFS 모두 가능하지만, 다른 문제를 풀면서 BFS를 더 많이 사용해서 이번에는 DFS를 사용해 문제를 풀어보기로 했다

 

dfs(int) 를 통해 방문한 노드를 넘겨주고, 만약 해당 노드를 방문했다면 return, 아니라면 연결된 노드를 다시 dfs로 탐색하였다.

방문한 노드의 visit값을 true로 변경하고, 새로운 노드를 방문할 때마다 ans값을 증가시켜 카운트했다.

결과값은 1번 컴퓨터가 감염시킨 컴퓨터의 수이므로 1번 컴퓨터를 제외하기 위해 결과에 -1을 해주면 된다

 

코드

import java.util.Scanner;

public class Main {
    static int N, ans;
    static boolean[] visit;
    static boolean[][] adj;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        visit = new boolean[N + 1];
        adj = new boolean[N + 1][N + 1];
        int m = sc.nextInt();

        for (int i = 0; i < m; i++) {
            int n1 = sc.nextInt(), n2 = sc.nextInt();

            adj[n1][n2] = adj[n2][n1] = true;
        }

        dfs(1);
        System.out.println(ans - 1);

    }

    static void dfs(int n) {
        if (visit[n])
            return;

        visit[n] = true;
        ans++;
        for (int i = 1; i <= N; i++) {
            if (adj[n][i])
                dfs(i);
        }
    }
}

 

제출 결과