[Baekjoon] 2606 - 바이러스

📝 문제

 

 

 

🔑 풀이 과정

기본적인 DFS 문제.

 

인접행렬을 이용해 두 노드사이에 간선을 기록 후 시작점인 1인 DFS를 해준다.

DFS 완료 후, 방문 배열을 인덱스 2부터 끝까지 검사하면서 방문한 노드(true)의 개수를 세준다.

(왜 인덱스 2부터 시작이냐면 구하는 것이 "1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수" 이기 때문에 1번 컴퓨터를 제외한 나머지 컴퓨터의 바이러스 감염 여부를 따지는 것)

 

 

 

🔓 답안

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int[][] A;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int C = Integer.parseInt(br.readLine());
        int E = Integer.parseInt(br.readLine());
        A = new int[C+1][C+1];
        visited = new boolean[C+1];
        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A[a][b] = 1;
            A[b][a] = 1;
        }

        DFS(1);

        int count = 0;
        for(int i = 2; i <= C; i++){
            if(visited[i])
                count++;
        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();

    }

    static void DFS(int s){
        if(visited[s]){
            return;
        } else{
            visited[s] = true;
            for(int i = 1; i < A[s].length; i++){
                if(A[s][i] == 1)
                    DFS(i);
            }
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색