Java 백준 문제풀이 (31) 2606: 바이러스

 

 

 

 

 

 

문제 요약  -  1번 정점에서 탐색할 수 있는 정점 개수를 구하시오.

 

" 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터 수 "라서 1번은 제외하고 카운트한다.

dfs, bfs 어떤 방식을 채택해도 풀 수 있지만 나는 코드가 짧은 dfs 알고리즘이 좋다.

이번 문제는 친절하게 그림까지 그려져 있어서 설명하는 척이라도 할만한 건덕지가 없다.. 날로 먹는군.

 

 

 

 

 

 

 

 

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

public class Main {
    static ArrayList<ArrayList<Integer>> edgeList = new ArrayList<>();
    static boolean[] visited;
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 컴퓨터 수(정점)
        int computers = Integer.parseInt(br.readLine());
        // 연결되어 있는 컴퓨터 쌍의 수(간선)
        int edges = Integer.parseInt(br.readLine());

        // 정점 생성(시작 번호 1)
        for (int i=0; i<computers+1; i++) {
            edgeList.add(new ArrayList<>());
        }

        // 간선 배열(무방향) 생성
        for (int i=0; i<edges; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int edge1 = Integer.parseInt(st.nextToken());
            int edge2 = Integer.parseInt(st.nextToken());

            edgeList.get(edge1).add(edge2);
            edgeList.get(edge2).add(edge1);
        }

        // 방문 체크 배열 생성 (시작이 1번)
        visited = new boolean[computers+1];

        dfs(1);

        System.out.println(count);
    }

    static void dfs(int computerNum) {
        // 이미 방문한 정점은 체크하지 않음
        visited[computerNum] = true;

        // 해당 컴퓨터(정점)에서 연결된 다른 컴퓨터(정점) 탐색
        for ( int n : edgeList.get(computerNum) ) {
            if ( !visited[n] ) {
                // 아직 방문하지 않았을 경우
                dfs(n);
                count++;
            }
        }
    }
}