[백준 2606] 바이러스

 

그래프에 대해 공부해 보았다면 DFS 로 풀 수 있는 문제란걸 유추할 수 있다.

 

연결된 정보를 가지고 문제를 푼다 -> 그래프 문제

만든 그래프로 최단거리, 최소거리를 구해야 한다 -> BFS

그렇지 않다 -> DFS

 

 

네트워크 연결이 한방향으로만 되지는 않을것이고 별도의 언급도 없으니 양방향 그래프라고 볼 수 있다.

2차원 배열로 그래프를 만들어 노드마다 연결된 노드 번호를 매겨주고 카운트를 세어주면 된다.

노드 탐색을 할때 연결된 노드를 전부 탐색한 뒤 재귀호출 하는 방식으로 구성하고 싶어서 큐를 이용했다.

 

public class Main {
    
    static int n;
    static int a[][];
    static boolean visited[];
    static Queue<Integer> q = new LinkedList<Integer>();
    static int cnt = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        a = new int[n+1][n+1];
        visited = new boolean[n+1];
        int m = sc.nextInt();
        while(m-->0) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            a[x][y] = y;
            a[y][x] = x;
        }
        
        visited[1] = true;
        dfs(1);
        System.out.println(cnt);
    }
    
    public static void dfs(int x) {
        for(int i=1; i<=n; i++) {
            if(a[x][i] != 0 && !visited[i]) {
                visited[i] = true;
                q.offer(a[x][i]);
                cnt++;
            }
        }
        while(!q.isEmpty()) {
            dfs(q.poll());
        }
    }
}