작성 코드

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

public class virus_2606 {
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());

        graph = new ArrayList[v + 1];
        for (int i = 0; i < v+1; i++){
            graph[i] = new ArrayList<>();
        }

        visited = new boolean[v + 1];

        for (int i = 0; i < w; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

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

        int start = 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        int count = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int next : graph[node]) {
                if (!visited[next]) {
                    count++;
                    queue.offer(next);
                    visited[next] = true;
                }
            }
        }

        System.out.println(count);
    }
}

설명

주어진 코드는 바이러스의 전파를 나타내는 그래프에서 1번 노드부터 시작하여 BFS(Breadth-First Search)를 수행하여 전체 감염된 노드의 수를 계산하는 로직입니다. 아래는 해당 코드의 로직을 설명한 것입니다.

• 입력으로 주어지는 노드 수(v)와 간선 수(w)를 읽어옵니다.
• graph 배열을 초기화합니다. graph는 각 노드의 인접 리스트를 저장하는 배열로, 각 노드에 연결된 인접한 노드들을 저장합니다.
• visited 배열을 초기화합니다. visited는 각 노드의 방문 여부를 저장하는 배열로, 방문한 노드는 true로 표시됩니다.
• 간선 정보를 입력받아 graph 배열에 저장합니다. 입력으로 주어지는 두 노드 사이에 양방향 간선이 존재하므로, 양쪽 방향으로 간선을 추가합니다.
• BFS를 수행하기 위해 시작 노드 1을 큐(queue)에 삽입하고, 해당 노드를 방문 처리합니다.
• 전체 감염된 노드의 수를 저장하는 변수 count를 초기화합니다.
• 큐가 비어있을 때까지 다음 과정을 반복합니다:
  • 큐에서 노드(node)를 꺼냅니다.
  • 현재 노드(node)와 인접한 노드(next)를 순회합니다.
  • 인접한 노드(next)가 방문되지 않은 경우, 감염된 노드의 수(count)를 증가시키고, 인접한 노드를 큐에 삽입하고 방문 처리합니다.
• BFS가 종료되면 count 값을 출력합니다. 이 값은 시작 노드인 1번 노드를 통해 감염된 전체 노드의 수를 나타냅니다.

자바스크립트

const readline = require("readline");
let v, w;
const graph = [];
const input = [];

readline
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    v = parseInt(input[0]);
    w = parseInt(input[1]);

    const visited = new Array(v + 1).fill(false);

    for (let j = 0; j < v + 1; j++) {
      graph.push(new Array());
    }

    for (let i = 2; i < input.length; i++) {
      const [a, b] = input[i].split(" ").map(Number);
      graph[a].push(b);
      graph[b].push(a);
    }

    const queue = [];
    queue.push(1);
    visited[1] = true;
    let count = 0;

    while (queue.length > 0) {
      const node = queue.shift();

      for (const next of graph[node]) {
        if (!visited[next]) {
          count++;
          queue.push(next);
          visited[next] = true;
        }
      }
    }

    console.log(count);
    process.exit();
  });

파이썬

from collections import deque

v = int(input())
w = int(input())
graph = [[] for _ in range(v + 1)]
visited = [False] * (v + 1)

for _ in range(w):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

start = 1
queue = deque()
queue.append(start)
visited[start] = True
count = 0

while queue:
    node = queue.popleft()

    for next_node in graph[node]:
        if not visited[next_node]:
            count += 1
            queue.append(next_node)
            visited[next_node] = True

print(count)