백준 2606번 : 바이러스(Java)

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

2606번: 바이러스

 

---

[풀이]

 

 바이러스는 연결되어 있는 컴퓨터 모두에게 전파되므로 연결되어있는 모든 컴퓨터를 탐색하면서 count++를 하면 된다. DFS를 이용해서 문제를 풀었으며 DFS는 스택을 이용해서 구현했다. 

 

 주어진 입력값에 맞게 2차원 배열에 연결되어있는 부분은 1로, 그렇지 않으면 0으로 초기화를 한 후, 방문하지 않은 곳은 visited 배열에 false로, 방문한 곳은 true로 값을 수정하면서 구현했다. 문제를 풀며 신경쓸 부분은 DFS를 구현하는 부분이었다.

 

---

[풀이]

 

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

class Main {
    static int[][] arr;
    static boolean[] visited;
    static int N, K;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bufferedReader.readLine());
        K = Integer.parseInt(bufferedReader.readLine());

        arr = new int[N + 1][N + 1];
        visited = new boolean[N + 1];

        for (int i = 1; i <= K; i++) {
            String line = bufferedReader.readLine();
            StringTokenizer st = new StringTokenizer(line, " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            arr[a][b] = 1;
            arr[b][a] = 1;
        }

        dfs(1);
        
        System.out.println(count);
    }

    public static void dfs(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        visited[start] = true;

        while (!stack.isEmpty()) {
            for (int i = 1; i <= N; i++) {
                if (arr[start][i] == 1 && visited[i] == false) {
                    stack.push(i);
                    visited[i] = true;
                    count++;
                    dfs(i);
                }
            }
            stack.pop();
        }
    }
}