백준 2606번 : 바이러스 자바

백준 2606번

2606번: 바이러스

 

문제

---

 

풀이

---

 

그래프에서 1번 컴퓨터(노드)를 시작점으로 연결되어있는 컴퓨터들은 모두 바이러스에 감염된 것이기에

BFS , DFS 둘다 사용하여 풀 수 있다. 

 

이번에는 DFS를 사용하여 풀었다. 

재귀호출 , Stack 두 가지 경우를 둘다 사용해보았다.

 

 

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

public class Main {

    static int[][] graph;
    static boolean[] visited;
    static int V,E,count;


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

        V = Integer.parseInt(br.readLine());
        E = Integer.parseInt(br.readLine());

        // 1부터 시작
        graph = new int[V + 1][V + 1];
        visited = new boolean[V+1];

        int v1,v2;

        // 그래프 초기화
        for (int i = 0; i < E; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());

            graph[v1][v2] = graph[v2][v1] = 1;

        }

        dfs_stack(1);

        bw.write(count + "");
        bw.flush();
        bw.close();
    }

    public static void dfs(int startN) {

        visited[startN] = true;

        for (int i = 1; i <= V; i++) {
            if (graph[startN][i] == 1 && !visited[i]) {
                count++;
                dfs(i);
            }

        }

    }

    public static void dfs_stack(int startN) {

        Stack<Integer> stack = new Stack<>();

        visited[startN] = true;
        stack.push(startN);

        while (!stack.isEmpty()) {
            int node = stack.pop();

            for (int i = 1; i <= V; i++) {
                if (graph[node][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    stack.push(i);
                    count++;
                }
            }
        }

    }

}

 

 

한 번 비슷한 문제를 풀고 나니 쉬웠다.