[백준(JAVA)] 2606번: 바이러스

세하·2025년 5월 25일

Java booleanVSBoolean 그래프 이론 그래프 탐색 깊이 우선 탐색 너비 우선 탐색 백준 인접 리스트

[백준] 문제풀이

목록 보기

61/94

문제

✔ 난이도 - Silver 3

설명

그래프 탐색 문제이며 DFS, BFS 두 가지 방법으로 모두 풀 수 있다.
https://velog.io/@seha01130/DFSDepth-First-Search-깊이우선탐색
https://velog.io/@seha01130/BFSBreadth-First-Search-너비우선탐색

그래프 탐색
어떤 정점(노드)에서 시작해서 연결된 모든 노드를 방문하는 방법

해결순서

입력받은 연결 정보를 그래프로 표시하기 -> 인접 리스트 형태로 저장
1번 컴퓨터부터 dfs나 bfs를 사용하여 탐색
1번 컴퓨터는 제외이므로 갯수에서 1을 뺀 것이 답이다.

풀이 (DFS 이용)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

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

        int n = Integer.parseInt(br.readLine()); //컴퓨터 수
        int m = Integer.parseInt(br.readLine()); //연결된 쌍의 수

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

        StringTokenizer st;
        for (int i = 0; i < m; 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);
        }
        // ----------------- 간선 정보 입력 완료

        // 방문여부 체크
        boolean[] visited = new boolean[n+1];

        int count = dfs(1, graph, visited, 0) - 1;
        sb.append(count);
        System.out.println(sb);
    }

    static int dfs(int node, ArrayList<Integer>[] graph, boolean[] visited, int count){
        visited[node] = true;
        count++;

        for (int next : graph[node]) {
            if (!visited[next]) { // 아직 방문 안했으면
                count = dfs(next, graph, visited, count);
            }
        }
        return count;
    }
}

풀이 (BFS 이용)

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

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

        int n = Integer.parseInt(br.readLine()); //컴퓨터 수
        int m = Integer.parseInt(br.readLine()); //연결된 쌍의 수

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

        StringTokenizer st;
        for (int i = 0; i < m; 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);
        }
        // ----------------- 간선 정보 입력 완료

        // 방문여부 체크
        boolean[] visited = new boolean[n+1];

        int count = bfs(1, graph, visited);
        sb.append(count);
        System.out.println(sb);
    }

    static int bfs(int node, ArrayList<Integer>[] graph, boolean[] visited){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(node);
        visited[node] = true; //넣을때 true로 해주는게 맞음. 그래야 중복으로 enqueue하지 않음.
        int count = 0;

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

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

⏰ 시간복잡도

DFS와 BFS의 시간 복잡도는 그래프의 노드 수(V)와 간선 수(E)에 따라 계산됨
인접 리스트로 구현한 경우 시간복잡도는 O(V + E)

모든 노드를 한 번씩 방문 (visited 배열로 방문체크를 함) -> O(V)
각 노드에서 연결된 간선을 모두 확인 -> 전체적으로 O(E)
즉, 정점마다 연결된 간선을 다 확인하므로 O(V + E)

만약 인접 행렬을 사용한다면 graph[i][j]를 모두 확인해야하므로 O(V²)

대부분의 코딩테스트에서는 인접 리스트 + O(V + E) 기반 DFS/BFS를 사용

TIL💡

📌 인접 리스트

그래프는 여러 노드들이 여러 간선들로 연결된 구조인데 이 그래프를 저장하는 대표적인 방법 중 하나.
각 노드에 연결된 노드들을 리스트 형태로 저장하는 방법.

1 -- 2
|    |			이런 무방향 그래프가 있을 때 인접리스트는
3    4
									.
graph[1] = [2, 3]
graph[2] = [1, 4]
graph[3] = [1]
graph[4] = [2]

각 인덱스(노드 번호)에 연결된 노드들을 ArrayList에 담은 것이다.

연결 정보를 인접 리스트 형태로 담는 예시코드

int n = 4;
List<Integer>[] graph = new ArrayList[n + 1]; // 1번부터 쓰기 위해 n+1

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

// 간선 추가 (무방향)
graph[1].add(2);
graph[1].add(3);
graph[2].add(1);
graph[2].add(4);
graph[3].add(1);
graph[4].add(2);