[JAVA] 백준 "바이러스"

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

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

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);
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}