[백준/자바] 2606번 바이러스

 

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

2606번: 바이러스

import java.util.ArrayList;
import java.util.Scanner;
public class March21 {
    public static boolean isvisited[];
    public static ArrayList<ArrayList<Integer>> graph=new ArrayList<ArrayList<Integer>>();
    public static int count=0;

    public static void dfs(int x, boolean visited){
        isvisited[x]=true;
        count++;
        for(int i=0;i<graph.get(x).size();i++){
            int y=graph.get(x).get(i);
            if(!isvisited[y]){
                dfs(y,isvisited[y]);
            }
        }
    }


    public static void main(String[] args){
        // BOJ 2606 바이러스
        Scanner s=new Scanner(System.in);
        int number=s.nextInt();
        int network=s.nextInt();

        for(int i=0;i<number+1;i++){
            graph.add(new ArrayList<Integer>());
        }

        isvisited=new boolean[number+1];

        for(int i=0;i<network;i++){
            int a=s.nextInt();
            int b=s.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        dfs(1,isvisited[1]);
        System.out.println(count-1);


    }

}

DFS를 공부하고 관련된 문제를 풀어보았다.

첫번째엔 런타임에러가 떴는데 graph와 isvisted가 0번을 안쓰고 넘어가기 때문에 +1을 안해줘서 나왔다.

두번째엔 틀렸나고 나와서 왜 그런가 한참을 들여다보고, 질문하기란에서 반례 찾아서 넣어보고 했다. 

5
4
1 2
3 2
4 2
5 2

해당 테스트케이스의 경우 2컴퓨터만 감염된다고 답이 나와서 왜 그런가하고 봤더니, 그래프가 무방향인데 입력을 마치 방향처럼 받고 있었기 때문에 그것을 고쳐주었다.

 //수정 전
 for(int i=0;i<network;i++){
            graph.get(s.nextInt()).add(s.nextInt());
        }
 //수정 후  
 for(int i=0;i<network;i++){
            int a=s.nextInt();
            int b=s.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }