[백준/Java] 2606 - 바이러스

http://acmicpc.net/problem/2606

문제

---

풀이

dfs로 구현 가능한 문제이다

연결되어 있는 컴퓨터를 표시하기 위해 com[][] 배열을 만들고 입력값에 맞게 com[x][y], com[y][x]를 1로 초기화한다

dfs를 돌면서 방문한 노드는 true로 해주고 감염된 컴퓨터 수를 +1 해준다

연결된 컴퓨터만 체크하고 방문하지 않은 노드일 때만 dfs 함수를 적용한다

코드

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

public class Main {

    static int[][] com;
    static boolean[] visited;
    static int cnt = 0;

    static int N;
    public static void main(String[] args) throws Exception {
        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());

        com = new int[N + 1][N + 1];
        visited = new boolean[N + 1];

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

        dfs(1);

        System.out.println(cnt - 1);
    }

    static void dfs(int start) {
        visited[start] = true;
        cnt++;

        for (int i = 0; i <= N; i++) {
            if (com[start][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
}

결과