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

✉️문제

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

2606번: 바이러스

 

📝 접근

이 문제를 풀기 위해서는 2가지를 알아야 한다.

 

DFS 또는 BFS

-> 본인은 DFS를 통해 문제를 풀었다.

-> DFS의 핵심은 재귀이며, 똑같은 정점을 방문하지 않도록 추가적인 체크배열이 필요하다.

public static void DFS(int idx) {
    ch[idx] = 1;
    for(int n : graph.get(idx)) {
        if(ch[n] == 0) {
            answer++;
            DFS(n);
        }
    }
}

 

인접 행렬

-> 1번 컴퓨터와 연결된 2번 5번을 인접 행렬로 표현하면 다음과 같다. (연결된 컴퓨터는 방향이 없기 때문에 1 -> 2,  2 -> 1 서로 연결해주어야 한다)

int[][] graph = new int[5][5];
graph[1][2] = 1;
graph[2][1] = 1;

graph[1][5] = 1;
graph[5][1] = 1;

 

 

🗝 문제풀이

import java.util.ArrayList;
import java.util.Scanner;

public class B2606 {

    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch;
    static int answer;

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

        int n = sc.nextInt(); // 컴퓨터 수
        int m = sc.nextInt(); // 연결 쌍
        ch = new int[n+1];

        graph = new ArrayList<>();
        for(int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for(int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        DFS(1);
        System.out.println(answer);
    }

    public static void DFS(int idx) {
        ch[idx] = 1;
        for(int n : graph.get(idx)) {
            if(ch[n] == 0) {
                answer++;
                DFS(n);
            }
        }
    }
}