[백준 2606/자바] 바이러스

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

 

---

 

BFS에 익숙해져보려고 계속 하는데 익숙해지지가 않음

더 공부해야 할 듯

 

✨ 참고
인접 리스트 - https://ko.wikipedia.org/wiki/%EC%9D%B8%EC%A0%91_%EB%A6%AC%EC%8A%A4%ED%8A%B8

---

풀이

BFS 및 인접 리스트 사용

 

📌 인접 리스트
그래프 이론에서 그래프를 표현하기 위한 방법 중 하나
그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법
인접 행렬에 비하여 변이 희소한 그래프에 효율적이다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

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

        int numComputers = Integer.parseInt(br.readLine());
        int numPairs = Integer.parseInt(br.readLine());

        /**
         * 네트워크를 표현하는 인접 리스트
         * 각 인덱스 번호의 컴퓨터와 연결된 컴퓨터를 저장함
         * 컴퓨터 번호가 1번부터 시작하므로 저장하기 쉽도록 0번 인덱스는 제외
         */
        List<List<Integer>> network = new ArrayList<>();
        for (int i = 0; i < numComputers + 1; i++) {
            network.add(new ArrayList<>());
        }

        // 네트워크 연결 입력 받기
        for (int i = 0; i < numPairs; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            network.get(a).add(b);
            network.get(b).add(a);
        }

        // BFS로 바이러스 전파 추적
        boolean[] visited = new boolean[numComputers + 1];  // 방문 컴퓨터
        Queue<Integer> queue = new LinkedList<>();  // BFS 탐색 위한 큐

        // 1번 컴퓨터
        queue.add(1);
        visited[1] = true;

        int count = 0;

        /**
         * 1) 큐에서 컴퓨터 번호를 꺼내온 후, 해당 컴퓨터와 연결된 컴퓨터들부터 확인
         *    --> network.get 함수 이용해 리스트 가져온 뒤 for문으로 확인
         * 2) 아직 방문하지 않은 컴퓨터일 경우 방문 표시 및 count + 1 한 뒤 큐에 추가
         * 3) 이미 방문한 컴퓨터인 경우 앞서 확인했던 컴퓨터와 연결 돼있다는 뜻
         * 
         * 큐가 빌 때까지 위 과정 반복
         */
        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int next : network.get(current)) { // current 번호의 컴퓨터와 연결된 컴퓨터 리스트
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                    count++;
                }
            }
        }

        System.out.println(count);
    }

}