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

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

2606번: 바이러스

풀이

이 문제는 그래프를 그리고 DFS혹은 BFS중 원하는것으로 하나를 선택해 탐색해 방문한 노드의 개수를 구하면된다.

나는 여기서 ArrayList속 ArrayList를 넣어 인접연결리스트를 구현하여 그래프를 구성했다. 그리고 만들어지 그래프에서 (1에서 시작하여) 현재위치의 노드에서 인접한 노드들의 번호를 큐에 넣는다. 그리고 큐에서 차례대로 뽑아서 만약 방문하지 않았다면 방문처리를 하고 위의 작업을 큐가 빌때까지 반복한다.

 

코드  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

    static int cnt_pc, cnt_relation;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        cnt_pc = Integer.parseInt(br.readLine());
        cnt_relation = Integer.parseInt(br.readLine());

        visit = new boolean[cnt_pc+1];
        visit[0] = true;

        for (int i = 0; i <= cnt_pc; i++) {
            list.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < cnt_relation; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            list.get(s).add(e);
            list.get(e).add(s);
        }

        BFS(1);
        br.close();

    }

    public static void BFS(int start){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        int result = 0;

        while(!queue.isEmpty()){
            int now = queue.poll();

            if(visit[now])
                continue;

            visit[now] = true;
            result++;

            for (Integer integer : list.get(now)) {
                queue.add(integer);
            }

        }

        System.out.println(result-1);
    }

}