[JAVA] 백준 2606번 - 바이러스

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

2606번: 바이러스

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static int n, m;
    public static boolean[] visit;
    public static int[][] arr;
    public static int cnt=0;

    public static void dfs(int v){
        if(visit[v]) return;

        visit[v] = true; // 방문 체크
        cnt++;

        for(int i=0; i<arr[v].length; i++){ // 인접행렬 탐색
            if(arr[v][i]==1 && !visit[i]) // 연결되어있으면서 방문하지 않은 노드인 경우
                dfs(i);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine()); // 노드 개수
        m = Integer.parseInt(br.readLine()); // 간선 개수

        arr = new int[n+1][n+1]; // 인접행렬 표현한 배열
        visit = new boolean[n+1]; // 노드 방문 여부 체크 배열

        for(int i=0; i<m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b]=arr[b][a] = 1; // 양방향 그래프
        }

        dfs(1);

        System.out.println(cnt-1); // 처음 1번 방문 제외 
    }
}

 

dfs로 풀었다.

입력받은 노드의 쌍을 배열에 1로 저장하고, 1번 노드부터 출발하여 인접한 노드가 아직 방문하지 않은 노드일 경우 

dfs함수를 호출하며 카운트를 증가시킨다.