[백준] 2606번 바이러스

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   네트워크 망을 통해 연결된 모든 컴퓨터를 감염시키는 바이러스가 있을 때 감염된 컴퓨터의 수를 구하는 문제이다.

 

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

 

   위와 같이 연결되어 있을 때 1번이 감염되면 2, 3, 5, 6번이 모두 감염되지만 4, 7번의 경우는 네트워크 망이 달라 영향을 받지 않는다.

   첫째 줄에는 컴퓨터의 수, 둘째 줄에는 연결된 컴퓨터 쌍의 수, 이어서 그 수만큼 한 줄에 한 쌍씩 컴퓨터의 번호 쌍이 입력된다. 제한 사항은 다음과 같다.

 

• 1 ≤ 컴퓨터의 수 ≤ 100
• 감염되는 컴퓨터는 항상 1번이다.
• 컴퓨터의 번호는 1번부터 컴퓨터의 수까지이다.

---

접근 방식

   BFS 개념을 이용해 1번과 연결된 컴퓨터를 감염 시킨 후, 감염된 컴퓨터를 기준으로 다시 연결된 컴퓨터를 탐색하였다. '문제 이해'에서의 예제를 통해 과정을 알아보자.

 

 

   1번의 감염 후 1번과 연결된 2, 5번이 감염된다.

 

 

   감염된 2, 5번에 대해 연결된 컴퓨터를 탐색한다. 2번에서 5번을 탐색하는 경우 5번은 이미 감염된(방문된) 상태이므로 5번으로 가는 경우의 수는 탐색할 필요가 없다. 5번에서 2번으로의 탐색 또한 마찬가지다.

 

 

   1번이 속한 네트워크 망 내에서의 탐색이 종료된다.

 

   컴퓨터 끼리의 연결관계를 단순히 그대로만 저장하게될 경우(연결관계에 방향성이 생길 경우) 문제가 발생한다. 만약 입력이 다음과 같이 주어진 경우를 생각해보자.

 

 

   위에서 설명했던 방식으로 진행되는 경우 1번에서 2번까지 탐색 후 2번에선 연결 관계를 찾을 수 없기 때문에 탐색이 종료된다. 즉, 3번을 탐색하기 위해선 연결된 두 번호가 모두 상대를 인지하고 있어야 한다.   

 

※ 1번을 통해 감염된 컴퓨터의 수를 구하는 것이기 때문에 1번의 감염은 결과에서 제외된다.

※ 방문 여부에 대한 판단이 잘못된 경우 무한 루프의 위험성이 있다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 백준2606번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;

    public static void main(String[] args) throws IOException {
        int total = Integer.parseInt(br.readLine());
        int connectNum = Integer.parseInt(br.readLine());
        //컴퓨터 별 연결관계를 저장할 큐배열
        Queue<Integer>[] connect = new Queue[total + 1];

        for (int i = 1; i <= total; i++)
            connect[i] = new LinkedList<>();
        for (int i = 0; i < connectNum; i++) {
            token = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(token.nextToken());
            int right = Integer.parseInt(token.nextToken());
            //연결관계를 양방향 저장
            connect[left].add(right);
            connect[right].add(left);
        }

        int count = 0;
        Queue<Integer> q = new LinkedList<>();
        //컴퓨터 방문 여부 판단을 위한 배열
        boolean[] valid = new boolean[total + 1];
        q.add(1);
        //1번 컴퓨터의 방문 여부 체크
        valid[1] = true;
        while (!q.isEmpty()) {
            int curNum = q.poll();
            //현재 컴퓨터와 연결된 컴퓨터 확인
            while (!connect[curNum].isEmpty()) {
                int nextNum = connect[curNum].poll();
                //이미 방문한 경우 수행 x
                if (valid[nextNum]) continue;
                valid[nextNum] = true;
                q.add(nextNum);
                //감염 횟수 증가
                count++;
            }
        }

        System.out.println(count);
    }
}