[백준] 2606번: 바이러스

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

📌 문제 탐색하기

입력 : 첫째 줄 - 컴퓨터의 수 (1 ≤ 컴퓨터의 수 ≤ 100)
두번째 줄 - 직접 연결되어 있는 컴퓨터의 쌍의 수
세번째 줄 - 직접 연결되어 있는 컴퓨터의 번호 쌍
두번째 줄의 수만큼 세번째 줄 반복
출력 : 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수

가능한 시간복잡도

O(V + E)
V : 정점의 수
E : 간선의 수

알고리즘 선택

BFS

📌 코드 설계하기

1. 컴퓨터의 수와 연결되어 있는 쌍의 수 및 번호 쌍을 입력 받는다.
2. 각 컴퓨터를 정점으로 연결된 컴퓨터를 리스트로 저장해 그래프를 구성한다.
3. 큐를 사용해 BFS 탐색을 시작한다.
4. 초기에 1번 컴퓨터를 큐에 추가해 방문 표시를 하고, 큐에서 컴퓨터를 하나씩 꺼내면서 연결된 컴퓨터를 탐색한다.
5. 연결된 컴퓨터에 아직 방문하지 않은 경우 큐에 추가하고 방문 표시를 한다.
6. 1번 컴퓨터와 연결된 모든 컴퓨터를 탐색하고, 웜에 감염된 컴퓨터의 수를 계산해 출력한다.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

import java.util.*;

public class Main {
    static boolean[] visited;
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numComputers = scanner.nextInt();
        int numConnections = scanner.nextInt();

        visited = new boolean[numComputers + 1];
        graph = new ArrayList[numComputers + 1];

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

        for (int i = 0; i < numConnections; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }

        scanner.close();
        System.out.println(bfs(1) - 1); // 1번 컴퓨터 제외
    }

    static int bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        int count = 0;

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

            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }

        return count;
    }
}