[백준/Java] 바이러스 2606 그래프 탐색(DFS)

 

문제

2606번: 바이러스

 

 

 

 

풀이

 

이 문제는 그래프 탐색을 통해 해결할 수 있으며, 1번 컴퓨터를 시작점으로 깊이 우선 탐색(DFS)을 수행하여 바이러스가 전파되는 컴퓨터의 수를 계산하였다.

각 컴퓨터 간 연결 관계는 인접 리스트로 표현하였고, 방문한 컴퓨터는 visited 배열로 체크하여 중복 감염을 방지하였다.

최종적으로 1번 컴퓨터를 제외한 감염된 컴퓨터의 수를 출력하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static List<Integer>[] network;
    public static boolean[] visited;
    public static int answer = 0;

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

        int computer = Integer.parseInt(br.readLine()); // 컴퓨터의 개수
        int node = Integer.parseInt(br.readLine()); // 컴퓨터 쌍의 수
        network = new ArrayList[computer + 1];
        visited = new boolean[computer + 1];

        for (int i = 0; i < network.length; i++) {
            network[i] = new ArrayList<>();
        }

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

            network[x].add(y); // 컴퓨터 연걸 짓기
            network[y].add(x);
        }

        dfs(1); // 1을 기준으로 탐색
        System.out.println(answer);

    }

    /**
     * dfs로 탐색하기
     * @param node
     */
    public static void dfs(int node) {
        visited[node] = true;

        for (int i = 0; i < network[node].size(); i++) {
            if (!visited[network[node].get(i)]) {
                answer++;
                dfs(network[node].get(i));
            }
        }
    }
}

 

 

정답