[220809][BC][백준](2606) 바이러스

[honeySleepr]

📌 문제

• 문제

⭐️ 아이디어

• List<List<Integer>>와 Queue를 활용한 BFS

🤔 고민한 내용

💪 새롭게 배운 내용

• 이 문제 처럼 경우의 수가 많지 않은 경우(컴퓨터 수 100개 이하) DFS를 활용하는게 풀이가 더 깔끔한 것 같다 (feat. Tany @juni8453)

🆘 이해가 어려운 내용

❌ 해결하지 못한 이유

✅ 본인 풀이

• DFS : 140, BFS : 144

/**
 * <h1>바이러스</h1>
 * <h3>도움!! : X</h3>
 * <h3>날짜 : 2022/08/09</h3>
 * <br><h2>comment : BFS 활용 </h2>
 */
public class BJ2606 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int C = Integer.parseInt(br.readLine());
        final int N = Integer.parseInt(br.readLine());
        List<List<Integer>> listlist = new ArrayList<>();
        for (int i = 0; i < C + 1; i++) { /* listlist.get(0)은 안쓴다. 칸 채우기 용 */
            listlist.add(new ArrayList<>());
        }
        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split("\\s");
            listlist.get(Integer.parseInt(split[0])).add(Integer.parseInt(split[1]));
            listlist.get(Integer.parseInt(split[1])).add(Integer.parseInt(split[0]));
        }

        Deque<Integer> queue = new ArrayDeque<>();
        boolean[] checkArr = new boolean[C + 1];
        queue.add(1);
        checkArr[1] = true;

        int count = 0;
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();

            for (Integer com : listlist.get(poll)) {
                if (checkArr[com]) {
                    continue;
                }
                checkArr[com] = true;
                count++;
                queue.add(com);
            }
        }

        System.out.println(count);
    }
}