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

 

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

 

- 정답 코드

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

// DFS 사용
// 감염된 컴퓨터의 수 계산
public class Main {
    static int node;  // 컴퓨터 수
    static int line; // 직접 연결 컴퓨터수 
    static int[][] arr;  // 연결 컴퓨터 쌍 저장 배열 
    static boolean[] visited; // 방문 여부 저장 배열
    static int birusCnt = 0; // 감염된 컴퓨터 수

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        node = Integer.parseInt(br.readLine()); // 7
        line = Integer.parseInt(br.readLine());  // 6
        arr = new int[node + 1][node + 1];
        visited = new boolean[node + 1]; 
        
        for(int i = 0; i < line; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()); // 1 2
            int a = Integer.parseInt(st.nextToken()); // 1
            int b = Integer.parseInt(st.nextToken()); // 2
            arr[a][b] = arr[b][a] = 1; // 연결된 컴퓨터 표시
        }

        dfs(1);

        System.out.println(birusCnt - 1);
    }

    private static void dfs(int start) {
        visited[start] = true; 
        birusCnt++;

        // 인접한 모든 노드 탐색
        for(int i = 0; i <= node; i++) {
            // 연결되어있고 아직 방문하지 않은 노드를 재귀적으로 탐색
            if(arr[start][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
}

---

- 코드 설명

 

1. 연결 정보 입력

for(int i = 0; i < line; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()); // 1 2
            int a = Integer.parseInt(st.nextToken()); // 1
            int b = Integer.parseInt(st.nextToken()); // 2
            arr[a][b] = arr[b][a] = 1; // 연결된 컴퓨터 표시
        }

 

• 예제 입력에 따라 arr 배열에 연결 정보를 저장합니다.
• 예: arr[1][2] = arr[2][1] = 1는 컴퓨터 1과 2가 연결되어 있음을 나타냅니다.
• 1-2, 2-3, 1-5, 5-2, 5-6, 4-7

 

 

2. DFS 탐색

private static void dfs(int start) {
        visited[start] = true; 
        birusCnt++;

        // 인접한 모든 노드 탐색
        for(int i = 0; i <= node; i++) {
            // 연결되어있고 아직 방문하지 않은 노드를 재귀적으로 탐색
            if(arr[start][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }

 

 

• 이 for 루프는 현재 노드 start와 연결된 모든 노드를 탐색합니다.
• i는 0부터 node까지의 인덱스를 가지며, 각 노드가 start와 연결되어 있는지 확인합니다.
• arr[start][i] == 1은 노드 start와 노드 i가 연결되어 있음을 의미합니다.
• !check[i]는 노드 i가 아직 방문되지 않았음을 의미합니다.
• 두 조건이 모두 참이면, dfs(i)를 호출하여 노드 i를 방문하고, 연결된 노드를 재귀적으로 탐색합니다.

 

 

[DFS 실행 흐름 예시]

예를 들어, 1번 컴퓨터에서 시작하여 다음과 같은 그래프가 주어졌다고 가정합시다:

1 - 2
2 - 3
1 - 5
5 - 6
4 - 7

 

1번 컴퓨터에서 DFS를 시작하면 다음과 같이 진행됩니다:

1. 1번 노드를 방문하고 count++.
2. 1번과 연결된 2번 노드를 방문하고 count++.
3. 2번과 연결된 3번 노드를 방문하고 count++.
4. 2번은 이미 방문되었으므로 다시 방문하지 않습니다.
5. 1번과 연결된 5번 노드를 방문하고 count++.
6. 5번과 연결된 6번 노드를 방문하고 count++.
7. 6번은 이미 방문되었으므로 다시 방문하지 않습니다.

 

 

3. 결과 출력

 System.out.println(birusCnt - 1);

감염된 컴퓨터 수에서 1번 컴퓨터를 제외한 수를 출력합니다.

 

dfs 메서드의 실행 흐름

1. 1번 노드에서 시작:
   • visited[1] = true로 1번 노드를 방문했음을 표시합니다.
   • birusCnt를 1 증가시킵니다.
2. 1번 노드와 연결된 노드 탐색:
   • for (int i = 0; i <= node; i++) 루프를 통해 1번 노드와 연결된 노드를 찾습니다.
   • arr[1][2] == 1이므로 2번 노드가 연결되어 있음을 확인하고, !visited[2]이므로 2번 노드가 아직 방문되지 않았음을 확인합니다.
   • dfs(2)를 호출하여 2번 노드를 방문합니다.
3. 2번 노드에서 탐색:
   • visited[2] = true로 2번 노드를 방문했음을 표시합니다.
   • birusCnt를 1 증가시킵니다.
   • 2번 노드와 연결된 노드(3번, 5번)를 찾고 방문합니다.
4. 3번 노드에서 탐색:
   • visited[3] = true로 3번 노드를 방문했음을 표시합니다.
   • birusCnt를 1 증가시킵니다.
   • 3번 노드와 연결된 노드(2번)가 이미 방문되었으므로, 더 이상 탐색하지 않습니다.
5. 5번 노드에서 탐색:
   • visited[5] = true로 5번 노드를 방문했음을 표시합니다.
   • birusCnt를 1 증가시킵니다.
   • 5번 노드와 연결된 노드(2번, 6번)를 찾고, 2번은 이미 방문되었으므로 6번을 방문합니다.
6. 6번 노드에서 탐색:
   • visited[6] = true로 6번 노드를 방문했음을 표시합니다.
   • birusCnt를 1 증가시킵니다.
   • 6번 노드와 연결된 노드(5번)가 이미 방문되었으므로, 더 이상 탐색하지 않습니다.