[백준알고리즘] dfs - 2606번 바이러스 문제

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

2606번: 바이러스

dfs만 구현하면 풀리는 문제

참고로 1번 컴퓨터는 제외한 수를 출력해야한다!

인접리스트 + dfs로 풀었다

 

package baekjoonWeek6;

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

public class BJ_2606 {  //백준 바이러스 문제
    static ArrayList<Integer>[] al;
    static int count;
    static int[] check;
    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 comCnt = Integer.parseInt(br.readLine());   //컴퓨터 개수
        int connect = Integer.parseInt(br.readLine());  //직접 연결된 컴퓨터 쌍 개수
        al = new ArrayList[comCnt + 1];
        for (int i = 0; i < comCnt + 1; i++) {
            al[i] = new ArrayList<Integer>();
        }
        int a; int b;
        for (int i = 0; i < connect; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            al[a].add(b);
            al[b].add(a);
        }
        check = new int[comCnt + 1];
        dfs(1);
        bw.write(Integer.toString(count - 1));  //1번 컴퓨터는 제외한다
        bw.flush();
        bw.close();
    }
    static void dfs(int x) {
        for (int i : al[x]) {
            if (check[i] == 0) {    //방문하지 않은 정점이면
                check[i] = 1;
                count++;
                dfs(i);
            }
        }
    }
}