백준 - 2606 바이러스 [BFS]

 

2606번: 바이러스

 

1. 문제 요약

컴퓨터의 수 n, 직접 연결된 컴퓨터의 수 m, 연결된 컴퓨터 쌍의 번호가 주어진다.

1번 컴퓨터와 직간접적으로 연결되어 있는 컴퓨터의 수를 구하시오.

 

2. 접근 방법

BFS(너비 우선 탐색) 알고리즘을 활용합니다.

• 1번을 기준으로 찾으면 되기 때문에, 4번과 7번은 무시합니다.
• 방문할 리스트를 생성하고 해당 리스트의 맨 앞부분에 1번을 추가합니다. (Deque 추천)
• 방문 리스트의 맨 앞 인덱스부터 순차적으로 방문합니다.
  • 1번을 방문합니다.
    • 1번을 방문했다는 표시를 합니다.
    • 1번에서 방문할 수 있는 번호 중, 방문하지 않은 번호(2,5)를 방문할 리스트의 뒷부분에 추가해 줍니다.
  • 2번을 방문합니다.
    • 2번을 방문했다는 표시를 합니다.
    • 2번에서 방문할 수 있는 번호 중, 방문하지 않은 번호(3,5)를 방문할 리스트의 뒷부분에 추가해 줍니다.
• 위 과정을 반복할 수 없을 때까지 반복합니다.

 

3. 파이썬

from sys import stdin
from collections import deque
input = stdin.readline

n = int(input())
m = int(input())
network = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    network[a].append(b)
    network[b].append(a)

virus = [0] * (n+1)

q = deque([1])
while len(q) > 0:
    computer = q.popleft()
    virus[computer] = 1

    for next_computer in network[computer]:
        if virus[next_computer] == 0:
            q.append(next_computer)

print(sum(virus) - 1)

 

4. 자바

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        int n = read();
        int m = read();
        boolean[] virus = new boolean[n + 1];
        Map<Integer, List<Integer>> network = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int a = read();
            int b = read();

            List<Integer> aOrDefault = network.getOrDefault(a, new ArrayList<>());
            aOrDefault.add(b);
            network.put(a, aOrDefault);

            List<Integer> bOrDefault = network.getOrDefault(b, new ArrayList<>());
            bOrDefault.add(a);
            network.put(b, bOrDefault);
        }

        int answer = -1;
        Deque<Integer> q = new ArrayDeque<>();
        q.add(1);
        while (!q.isEmpty()) {
            Integer computer = q.pollFirst();
            if (!virus[computer]) {
                virus[computer] = true;
                answer += 1;
            }

            if (network.get(computer) != null) {
                for (Integer nextComputer : network.get(computer)) {
                    if (!virus[nextComputer]) {
                        q.addLast(nextComputer);
                    }
                }
            }
        }

        System.out.println(answer);
    }

    // 읽기
    private static int read() throws Exception {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }
}