[JAVA] 백준 "바이러스"

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

 

간단히 BFS나 DFS를 통해서 시작노드1로부터 연결되어있는 지점을 방문처리하면 되는 문제다.

 

백준 테스트가 아직 적응이 안돼서, System.out.println으로 채점되는 것을 유의하지 못해서 시간을 질질 끌었다.

 

필자는 dfs로 방문하고 checked 가 true인 것의 개수를 세는 방식으로 체크하였다.

 

단, 1에서 전염시키는 컴퓨터의 수이므로 -1을 마지막에 해주어야한다.

 

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

public class Main {
    //함수에서 사용할 변수들
    static int[][] check; //간선 연결상태
    static boolean[] checked; //확인 여부
    static int n; //정점개수
    static int m; //간선개수
    static int start; //시작정점

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        start = 1;

        check = new int[n+1][n+1]; //좌표를 그대로 받아들이기 위해 +1해서 선언
        checked = new boolean[n+1]; //초기값 False

        //간선 연결상태 저장
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            check[x][y] = check[y][x] = 1;
        }

        dfs(start); //dfs호출

        int count = 0;
        for(boolean c : checked){
            if(c == true) count++;
        }
        if(count != 0) count--;
        System.out.println(count);
    }

    //시작점을 변수로 받아 확인, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출
    public static void dfs(int i) {
        checked[i] = true;
        //System.out.print(i + " ");

        for (int j = 1; j <= n; j++) {
            if (check[i][j] == 1 && checked[j] == false) {
                dfs(j);
            }
        }
    }
}