[백준 2606번] 바이러스

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

---

문제

---

아이디어

대표적인 DFS 문제이다. 예제 입력과 같이 두 노드를 입력 받아 그래프 탐색을 진행한다. DFS 구현에는 두 가지 방법이 있는데, 본 문제에서는 인접리스트를 이용하여 구현해보았다.

 

- 그래프 정보 입력

무방향 그래프로 입력 받기 위해 두 노드 서로에게 자식노드로 추가한다.

// 컴퓨터 정보 입력
for(int i=1; i<=M; i++) {
    String[] s = br.readLine().split(" ");
    int a = Integer.parseInt(s[0]);
    int b = Integer.parseInt(s[1]);
    computers[a].add(b);
    computers[b].add(a);
}

 

- 노드 탐색

기본적인 dfs 탐색 방식과 동일. 탐색 시작 노드는 '1'로 고정이므로, 이와 연결된 노드들에 대하여 탐색. 최종 출력 시 count는 초기 노드인 '1' 인 제외하고 출력할 것.(count - 1)

static void DFS(int start) {
    // 방문 하지 않은 노드 탐색
    if(!visited[start]) {
        visited[start] = true;
        count++;
        for(int i=0; i<computers[start].size(); i++) {
            DFS((int)computers[start].get(i));
        }
    }
}

---

전체 코드

package Baekjoon;

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

public class B_2606 {
    static int N, M;
    static boolean[] visited;
    static List[] computers;
    static int count = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N, M 입력
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        // 컴퓨터 초기화
        visited = new boolean[N+1];
        computers = new List[N+1];
        for(int i=1; i<=N; i++) {
            computers[i] = new ArrayList<>();
        }
        // 컴퓨터 정보 입력
        for(int i=1; i<=M; i++) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            computers[a].add(b);
            computers[b].add(a);
        }

        DFS(1);

        System.out.println(count-1);
    }
    static void DFS(int start) {
        // 방문 하지 않은 노드 탐색
        if(!visited[start]) {
            visited[start] = true;
            count++;
            for(int i=0; i<computers[start].size(); i++) {
                DFS((int)computers[start].get(i));
            }
        }
    }
}