[백준] CLASS3 2606 바이러스 - JAVA [자바]

안녕하세요. 이번에는 백준 2606 바이러스 문제를 풀어보려고 합니다.

 

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

2606번: 바이러스

---

Problem

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

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

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

사진 1. 문제

---

Solution

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

public class Main {
    
    static int computers;
    static int[][] tree;
    static boolean[] visited;
        
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        computers = Integer.parseInt(br.readLine());
        int networks = Integer.parseInt(br.readLine());
        
        tree = new int[computers + 1][computers + 1];
        visited = new boolean[computers + 1];
        
        StringTokenizer st;
        for(int i = 0; i < networks; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            
            tree[start][end] = tree[end][start] = 1; 
        }
        
        System.out.println(bfs());
    }
    
    static int bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        visited[1] = true;
        int count = 0;
        
        while(!q.isEmpty()) {
            int start = q.poll();  
            
            for(int i = 0; i <= computers; i++) {
                if(!visited[i] && tree[start][i] == 1) {
                    count++;
                    visited[i] = true;
                    q.offer(i);
                }    
            }
        }
        
        return count;
    }
}

 이번 문제는 Queue를 활용하여 문제를 풀면 되는 문제이다. tree 배열을 만들어준 후 start 지점과 네트워크가 연결되는 지점 end 지점을 넣어준 후 Queue에 시작지점 1을 넣고 연결되는 지점들은 Queue에 삽입하고, count++ 해주면서 visited 방문 체크를 해준다. 여기서 방문 체크를 하는 이유는 중복을 제거하기 위해서이다.  그렇게 Queue가 비어있을 때까지 반복해 주면 된다.

 

핵심 코드

while(!q.isEmpty()) {
	int start = q.poll();  
            
	for(int i = 0; i <= computers; i++) {
		if(!visited[i] && tree[start][i] == 1) {
			count++;
			visited[i] = true;
			q.offer(i);
		}    
	}
}

---

Performance

사진 2. 실행 결과