백준 2606번: 바이러스 문제 풀이 (Java로 구현한 BFS/DFS 알고리즘)

백준 2606번 "바이러스" 문제는 네트워크 상에서 바이러스의 감염 범위를 계산하는 문제로, 그래프 탐색 알고리즘인 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 활용하여 해결할 수 있습니다.
이 글에서는 Java를 사용해 구현한 풀이를 소개하고, 문제 해결 과정과 주요 알고리즘을 설명합니다.

---

1. 문제 개요

1.1 문제 설명

• 컴퓨터 네트워크에서 1번 컴퓨터가 바이러스에 감염되었을 때, 네트워크를 통해 감염되는 컴퓨터의 개수를 구하는 문제입니다.
• 컴퓨터는 노드로, 네트워크 연결은 엣지로 표현할 수 있어 그래프 탐색 문제로 접근할 수 있습니다.

---

1.2 입력 및 출력

1. 입력:
   • 첫 줄: 컴퓨터의 수 (노드의 개수).
   • 둘째 줄: 네트워크 연결 수 (엣지의 개수).
   • 이후 줄: 각 네트워크 연결 정보 (노드 간 연결).
2. 출력:
   • 바이러스에 감염된 컴퓨터의 수 (1번 컴퓨터 제외).

---

2. 문제 해결 방법

2.1 접근 방식

• 네트워크를 그래프로 표현.
• 1번 노드에서 시작하여 연결된 모든 노드를 탐색.
• 탐색 시 방문한 노드를 기록하여 중복 탐색 방지.
• DFS나 BFS를 사용하여 감염된 노드의 개수를 계산.

---

2.2 알고리즘 선택

• DFS:
  • 재귀 호출을 사용하여 깊이 우선으로 탐색.
  • 연결된 노드를 방문하고 다시 상위 노드로 돌아오는 방식.
• BFS:
  • 큐를 사용하여 너비 우선으로 탐색.
  • 가까운 노드부터 차례대로 방문.

---

3. Java 코드 설명

Java 코드

import java.util.*;

public class Main {
    static int[][] graph; // 그래프 연결 상태
    static boolean[] visited; // 방문 여부 기록
    static int count = 0; // 감염된 컴퓨터 수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 컴퓨터 수
        int m = sc.nextInt(); // 네트워크 연결 수

        graph = new int[n + 1][n + 1]; // 1-based index 사용
        visited = new boolean[n + 1];

        // 그래프 초기화
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = 1;
            graph[b][a] = 1; // 무방향 그래프
        }

        dfs(1); // 1번 컴퓨터에서 시작

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

    static void dfs(int node) {
        visited[node] = true;
        count++; // 감염된 컴퓨터 수 증가

        for (int i = 1; i < graph.length; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                dfs(i); // 연결된 노드 탐색
            }
        }
    }
}

3.1 주요 로직

1. 그래프 초기화:
   • 입력 데이터를 바탕으로 2차원 배열에 노드 간 연결 정보 저장.
   • graph[a][b] = 1로 연결 표시.
2. DFS 탐색:
   • dfs(int node)를 재귀적으로 호출.
   • 현재 노드와 연결된 노드를 순차적으로 탐색.
3. 방문 여부 체크:
   • visited 배열을 사용하여 이미 탐색한 노드는 재탐색하지 않도록 설정.
4. 결과 출력:
   • count는 1번 노드를 포함하므로, 최종 결과에서 -1을 계산.\

5. 핵심 포인트

1. DFS를 통한 깊이 우선 탐색:
   • 재귀 호출로 구현, 코드 간결.
   • 큰 그래프에서는 스택 오버플로우 가능성 있음.
2. 방문 배열의 활용:
   • 중복 탐색 방지.
   • 탐색 효율성 증가.
3. 그래프 표현 방식:
   • 2차원 배열로 연결 상태 표현(인접 행렬).

https://github.com/siilver94/Algorithm/blob/master/BfsDfs/2606.java

Algorithm/BfsDfs/2606.java at master · siilver94/Algorithm

 

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