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

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

---

● 문제

BFS를 약간 변형하여 해결할 수 있는 문제이다. 먼저 입력 받은 연결된 노드 쌍을 입력받고 1의 값을 넣어줍니다 그리고 visited는 해당 노드를 방문했는지 안했는지를 나타냅니다 이후 dfs는 재귀형식으로 구현하여 문제를 해결하였습니다.

 

처음에는 그래프 문제가 많이 어렵지만 역시 문제를 많이 풀어봐야된다고 느꼈습니다.

---

● 코드

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

public class Main {

    static boolean[] visited;
    static int[][] graph;
    static int count = 0;

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


        node = Integer.parseInt(br.readLine());
        line = Integer.parseInt(br.readLine());

        visited = new boolean[node+1];
        graph = new int[node+1][node+1];

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

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

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

        dfs(1);

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

    static void dfs(int nodeIndex) {
        visited[nodeIndex] = true;
        count++;

        for(int i = 0; i <= node; i++) {
            if(graph[nodeIndex][i] == 1 && !visited[i])
                dfs(i);
        }
    }
}