[BOJ] 2606 바이러스

바이러스

풀이

1) bfs

• bfs 기본 코드로 구현
• List 배열에 각 노드 인접 정점 저장
• visited 배열로 방문 확인
• 양방향 그래프로 구현
• bfs 로 순회하면서 queue에 정점 넣을 때마다 count 증가

2) dfs

• dfs 재귀로 구현
• 재귀 돌릴 때마다 count 증가
• visited 배열로 방문 확인
  
  

코드

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

public class BOJ2606 {
    static List<Integer>[] nodeList;
    static boolean[] visited;
    static int answer = 0;
    static Queue<Integer> queue = new LinkedList<>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); 
        int M = Integer.parseInt(br.readLine());
        nodeList = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            nodeList[i] = new ArrayList<>();
        }
        visited = new boolean[N];

        StringTokenizer st;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken())-1;
            int B = Integer.parseInt(st.nextToken())-1;
            nodeList[A].add(B);
            nodeList[B].add(A);
        }

        // bfs(0);
        dfs(0);
        System.out.println(answer);


    }

    private static void dfs(int i) {
        visited[i] = true;
        for (int next : nodeList[i]) {
            if (!visited[next])
            {
                answer++;
                dfs(next);
            }
        }
    }
    private static void bfs(int i) {
        visited[i] = true;
        queue.add(i);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : nodeList[cur]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                    answer++;
                }
            }
        }
    }
}