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

 

---

문제

• 컴퓨터 N대에 대해 각각 연결된 컴퓨터 번호가 주어질 때, 1번 컴퓨터가 바이러스에 걸리면 같이 바이러스에 감염되는 컴퓨터 대 수를 구하는 문제.

 

아이디어

• 그래프로 컴퓨터 연결을 구현하고, DFS 혹은 BFS 탐색을 통해 1번 컴퓨터랑 만 연결된 다른 컴퓨터들(노드들)의 개수를 파악한다.

 

풀이

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

public class Main {
    static int N, M;
    static boolean[][] graph;
    static boolean[] visited;
    static int answer = 0;

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

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

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

        int n1 = 0;
        int n2 = 0;
        // 그래프 간선 입력
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            n1 = Integer.parseInt(st.nextToken()) - 1;
            n2 = Integer.parseInt(st.nextToken()) - 1;
            graph[n1][n2] = true;
            graph[n2][n1] = true;
        }

        dfs(0);
        System.out.println(answer - 1);
    }
    
    // 컴퓨터 연결 관계 탐색
    static void dfs(int node) {
        answer++;
        visited[node] = true;
        for(int i=0; i<N; i++) {
            if(graph[node][i] && !visited[i]) {
                dfs(i);
            }
        }
    }
}

 

 

채점 결과

2606번 채점 결과

 

문제 링크

• 2606번: 바이러스 (acmicpc.net)