2606번 바이러스

2606 바이러스 //백준

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.


● 오답 사유
처음 이 문제를 봤을때 Set값을 이용해 값을 받고 감염된 값들을 모두 모아 검사하려 했지만 1번 컴퓨터가 중간이나 맨 밑에있을 경우 그 이전의 값들이 감염되었는지 확인이 불가능해 위아래를 반복하게 해서 했지만 중간 값을 받지 못해 틀렸다.

● 해결법
DFS와 BFS의 존제를 알았다. 그리고 서로  타입도 값도 다른 배열을 동일 인덱스의 순번이 같은 것을 이용해 간접적으로 이어붙여 만드는 방법을 알았다.

• 오답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Objects;
import java.util.Set;


public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Set<Integer> set = new HashSet<>();
        set.add(1);

        int m = Integer.parseInt(bf.readLine());
        int n = Integer.parseInt(bf.readLine());
        int[][] nn = new int[n][2];


        for (int i = 0; i < n; i++) {
            String[] nnn = bf.readLine().split(" ");
            nn[i][0]  = Integer.parseInt(nnn[0]);
            nn[i][1] =  Integer.parseInt(nnn[1]);
        }

        for (int i = 0; i < n; i++) {
            if(set.contains(nn[i][0])) {
                set.add(nn[i][0]);
            }if(set.contains(nn[i][1])) {
                set.add(nn[i][1]);
            }

        }

        System.out.println(set.size() == 1 ? "0" : set.size());

        
    }
}

• 정답

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 {
    static List<Integer>[] list ;;
    private static boolean[] vir;
    static int z = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int pc = Integer.parseInt(br.readLine());
        int cont = Integer.parseInt(br.readLine());
        list = new ArrayList[pc + 1];
        vir = new boolean[pc + 1];

        for (int i = 0; i <= pc; i++) {
            list[i] = new ArrayList<Integer>();
            vir[i] = false;
        }

        for (int i = 0; i < cont; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }

        zombie(1);

        System.out.println(z);
    }

     static void zombie(int pc) {
        if (vir[pc]) {
            return;
        }
        vir[pc] = true;
        if(pc != 1){
            z++;
        }
        for ( int t : list[pc]){
            if (!vir[t]){
                zombie(t);
            }
        }
    }


}