[백준 알고리즘] Q2606 바이러스 -BFS 너비탐색 알고리즘

1. Java 구현

            
package Q2606;

import java.io.*;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

public class Main {
    /*
	 	문제 : 다이얼
	 	url : https://www.acmicpc.net/problem/5622
	 	재풀이 : X
	*/

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 1. 입력값 초기화 //
        int countOfComputer = Integer.parseInt(br.readLine());
        int countOfPair = Integer.parseInt(br.readLine());
        int[][] arr = new int[countOfPair + 1][2];
        for (int i = 1; i < arr.length; i++) {
            String[] line = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(line[0]);
            arr[i][1] = Integer.parseInt(line[1]);
        }

        // 2. BFS 알고리즘 //
        Queue queue = new ConcurrentLinkedQueue<>();
        boolean[] visited = new boolean[countOfComputer + 1];

        queue.add(1);
        visited[1] = true;
        int answer = 0;
        while(!queue.isEmpty()) {
            int node = queue.poll();
            for(int i = 1; i < arr.length; i++) {
                if(arr[i][0] == node && visited[arr[i][1]] == false) {
                    visited[arr[i][1]] = true;
                    queue.add(arr[i][1]);
                    answer++;
                }
                if(arr[i][1] == node && visited[arr[i][0]] == false) {
                    visited[arr[i][0]] = true;
                    queue.add(arr[i][0]);
                    answer++;
                }
            }
        }

        System.out.println(answer);

    }
}

2. 코드설명

 이 문제는 BFS 너비탐색 알고리즘을 이용해서 풀 수 있다. BFS 너비탐색 알고리즘은 인접한 노드들을 탐색하고, 그 인접한 노드들을 계속해서 탐색하는
 방식이다. BFS를 풀기 위해서는 두가지의 자료구조가 필요하다. 첫번째는 이미 방문했던 노드들을 확인하기 위한 boolean 타입에 배열이 필요하다. 

 boolean 타입의 배열은 이미 방문했던 노드들을 중복적으로 방문하지 않기 위해 반드시 필요하다. 다음으로 필요한 것은 Queue이다.

 BFS에서 스택대신에 큐를 사용하는 이유는 스택은 LIFO 방식이기 때문에 마지막에 접근한 노드부터 꺼낼 수 있기 때문에 적합하지 않아서 이다.

 Queue에 인접한 노드들을 삽입하고, Queue에 있는 노드를 하나씩 꺼내서 꺼낸 노드와 인접한 노드를 큐에 삽입한다. 

 그리고 노드를 꺼내는 과정에서 boolean 타입의 배열을 이용해서 방문유무를 확인하여, 방문하지 않는 노드만 삽입한다. 

 이 과정을 계속 반복하면 인접한 노드들을 모두 탐색할 수 있다.