[Baekjoon] 2606번 바이러스(feat. Java)

접근

• 각 컴퓨터를 접점으로 취급한채로 간선을 이중배열로 연결 관계 표시
• 방문여부와 접점간에 연결여부를 통해 접근가능한지 확인

 

---

 

해결

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

public class Main {

    static int[][] arr1;
    static int[][] visited1;
    static HashSet<Integer> set;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        arr1 = new int[N+1][N+1];
        visited1 = new int[N+1][N+1];
        set = new HashSet<>();

        for(int i=0;i<M;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());

            arr1[X][Y] = arr1[Y][X] = 1;
        }

        dfs(1, N);

        System.out.println(set.size() - 1);
    }

    public static void dfs(int V, int N){
        int[] arr = arr1[V];

        set.add(V);

        for(int i=1;i<=N;i++){
            if(i == V)
                continue;

            if(arr[i] == 1 && visited1[V][i] == 0){
                visited1[V][i] = visited1[i][V] = 1;
                dfs(i, N);
            }
        }
    }
}