[백준 알고리즘 / JAVA] 2606번 바이러스

---

문제 정보

• 문제 링크: https://www.acmicpc.net/problem/2606
• 문제 번호: 2606번
• 문제 이름: 바이러스
• 문제 난이도: 실버3
• 반복 학습 날짜
  • 2024.01.16 완료
  • 2024.01.23 완료

2606번: 바이러스

---

코드

[첫 번째 코드]

import java.util.Scanner;

public class Main {
    static int[][] graph; // 컴퓨터 간 연결 정보를 저장할 배열
    static boolean[] visited; // 방문 여부를 체크할 배열
    static int count = 0; // 1번 컴퓨터와 연결된 컴퓨터의 수를 저장할 변수

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

        // 컴퓨터의 수와 연결된 간선의 수를 입력 받음
        int computerCount = scanner.nextInt();
        int edgeCount = scanner.nextInt();

        // 그래프와 방문 여부 배열 초기화
        graph = new int[computerCount + 1][computerCount + 1];
        visited = new boolean[computerCount + 1];

        // 간선 정보 입력 받아서 그래프에 저장
        for (int i = 0; i < edgeCount; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a][b] = graph[b][a] = 1; // 무방향 그래프이므로 양방향으로 연결
        }

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

        System.out.println(count); // 결과 출력
    }

    // 깊이 우선 탐색 (DFS) 메서드
    static void dfs(int node) {
        visited[node] = true; // 현재 노드 방문 표시

        // 현재 노드와 연결된 노드들에 대해서
        for (int i = 1; i < graph.length; i++) {
            // 연결되어 있고 아직 방문하지 않은 경우
            if (graph[node][i] == 1 && !visited[i]) {
                count++; // 연결된 컴퓨터 개수 증가
                dfs(i); // 연결된 노드에 대해 재귀 호출
            }
        }
    }
}

 

[두 번째 코드]

import java.util.*;

public class Main {
    public static int[][] graph;
    public static boolean[] visited;
    public static int count;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int computers = scanner.nextInt();
        int edges = scanner.nextInt();
        graph = new int[computers + 1][computers + 1];
        visited = new boolean[computers + 1];
        
        for(int i = 0; i < edges; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            graph[x][y] = graph[y][x] = 1;
        }
        
        DFS(1, computers);
        
        System.out.println(count);
    }
    
    public static void DFS(int vertex, int computers) {
        visited[vertex] = true;
        
        for(int i = 1; i <= computers; i++) {
            if(!visited[i] && graph[vertex][i] == 1) {
                count++;
                DFS(i, computers);
            }
        }
    }
}

---

풀이

Step1: DFS 깊이 우선 탐색 알고리즘 활용

// 깊이 우선 탐색 (DFS) 메서드
static void dfs(int node) {
    visited[node] = true; // 현재 노드 방문 표시

    // 현재 노드와 연결된 노드들에 대해서
    for (int i = 1; i < graph.length; i++) {
        // 연결되어 있고 아직 방문하지 않은 경우
        if (graph[node][i] == 1 && !visited[i]) {
            count++; // 연결된 컴퓨터 개수 증가
            dfs(i); // 연결된 노드에 대해 재귀 호출
        }
    }
}

 

 

DFS 알고리즘은 한 노드에서 시작하여 그래프를 탐색하고, 연결된 모든 노드를 방문하는 알고리즘입니다. 이를 통해 1번 컴퓨터에서 시작하여 바이러스에 걸린 컴퓨터를 찾아내고  바이러스에 걸린 컴퓨터의 개수를 세는 것이 문제의 핵심입니다.

 

위 코드에서 핵심 부분은 다음과 같습니다.

1. 1번 컴퓨터에서 DFS 알고리즘을 시작합니다.
2. 현재 컴퓨터와 연결된 컴퓨터를 확인하며 방문하지 않은 컴퓨터가 있으면 방문하고 연결된 컴퓨터의 개수를 증가시킵니다.
3. 2번을 반복하여 최초 1번에서부터 연결된 모든 컴퓨터를 탐색합니다.
4. 탐색이 끝나면 바이러스에 걸린 컴퓨터의 개수가 count에 저장됩니다.
5. 모든 그래프에 대해 DFS를 수행하므로 그래프 상에 존재하는 컴퓨터 중 바이러스에 걸린 컴퓨터를 찾을 수 있습니다.