[백준 2606 : JAVA] 바이러스 / BFS

개요

 

이 문제는 dfs와 bfs 알고리즘 둘 다 풀이가 가능하다.

두 알고리즘에 대해 기본을 익히고 싶다면 아래의 문제를 먼저 푸는 것을 추천한다.

 

2020/01/30 - [알고리즘/백준] - [백준 1260 : JAVA] DFS와 BFS / DFS, BFS

[백준 1260 : JAVA] DFS와 BFS / DFS, BFS

갈 수 있는 모든 노드의 개수를 구하면 풀이가 가능하다.

 

문제

 

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

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

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

 

입력

 

풀이

 

컴퓨터들을 노드라고 생각하고, 네트워크를 간선이라고 생각한다.

 

1. 큐에 시작 노드를 add()한다.
2. 큐에서 노드를 poll()한다.
3. 꺼낸 노드와 간선을 이루고 있는 노드를 add()한다.
   1. 추가한 노드를 방문처리한다.
4. 큐에 값이 존재하지 않을 때까지 2, 3을 반복한다.

 

 

코드

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 Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        boolean[][] isEdge = new boolean[n + 1][n + 1];
        boolean[] check = new boolean[n + 1];

        // 간선정보 초기화
        for(int i = 1; i <= m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int nodeA = Integer.parseInt(st.nextToken());
            int nodeB = Integer.parseInt(st.nextToken());

            // (1,2)가 간선이라면 (2,1)도 간선이다.
            isEdge[nodeA][nodeB] = isEdge[nodeB][nodeA] = true;
        }

        solve(isEdge, check, n);
    }
    
    // bfs로 풀이한다.
    public static void solve(boolean[][] isEdge, boolean[] check, int n){
        Queue<Integer> queue = new LinkedList<>();
        // 시작점 큐에 추가
        queue.add(1);
        check[1] = true;
        int ans = 0;

        while(!queue.isEmpty()){
            // 노드를 하나 꺼낸다.
            int num = queue.poll();
            // 갈수 있는 노드의 개수를 증가시킨다.
            ans++;

            for(int i = 1; i <= n; i++){
                // 현재 노드와 다른 노드 && 간선 존재 && 미방문한 노드
                if(i != num && isEdge[num][i] == true && check[i] == false){
                    queue.add(i);
                    // 방문 노드로 만듬
                    check[i] = true;
                }
            }
        }

        System.out.println(ans - 1);
    }
}