[백준] 2606: 바이러스 - Java (그래프 이론)

  목 차

• 문제
• 접근 방식
• 이 문제를 구현하며 알게된 것들
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

BFS Lover 인 나는 이 문제를 보았을 때 바로 BFS가 적합하다고 느꼈다.

 

BFS 방식이 언제나 그렇듯 하나씩 하나씩 근접한 값들을 큐에 넣어 돌리면 된다.

 

 

이 문제에서 주의할 점만 알면 30분 내로 풀 수 있는 문제인 것 같다. 

 

그 주의할 점은 바로.. 입력 값 한 쌍이 들어왔을 때, 한 쪽에만 값을 저장하는 행위이다.

 

예를 들면,

4
3
1 2
2 4
3 2

 

여기서 앞 쪽 숫자를 a 변수에, 뒤 쪽 숫자를 b 변수에 할당한다고 가정해 보자.

 

만약 graph[a].add(b); 만 하게된다면, 1, 2, 4는 연결이 되고, 3또한 연결이 되어있지만 출력 값에서는 낙오되는 현상을 볼 수 있다.

 

 

 

  이 문제를 구현하며 알게된 것들

 

저번 미로 탐색  부분에서는 배열 Queue 를 사용해서 문제를 구현하였는데, 알고보니 java.util 에서 제공하는 Queue 가 쓸만하다는 것을 느꼈다. 가독성에서나 성능에서나 전혀 뒤쳐지지 않는다. 애용해야 겠다.

 

알고리즘 문제를 풀면 그 언어에 대한 이해도가 점점 깊어지는 것이 느껴진다. 비록 지금은 낮지만 계속해서 땅을 파서 내려가자.

 

 

  풀이

 

설계 내용

 

package src.graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.List;
import java.util.StringTokenizer;

public class Virus {


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        List[] computers = new List[n+2];

        for(int i = 0; i <= n; i++){
            computers[i] = new ArrayList<>();
        }


        boolean[] isVisited = new boolean[n+2];


        // 입력 && 분류
        for(int i = 0; i < m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            computers[a].add(b);
            computers[b].add(a);
        }

        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);

        while(!queue.isEmpty()){

            int computer = queue.remove();

            isVisited[computer] = true;

            for(Object com : computers[computer]){
                int curCom = (int) com;

                if(isVisited[curCom]) continue;

                queue.add(curCom);

                isVisited[curCom] = true;

            }

        }

        int answer = 0;

        for(boolean el : isVisited){
            if(el == true) {
                answer = answer + 1;
            }

        }

        System.out.println(answer - 1);


    }

}