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

 

📝문제 설명

 

무방향 그래프 탐색 문제이다. 이 문제는 bfs, dfs 두 가지 방법으로 풀어 보겠다.

---

📢입출력 예시

 

- 정점의 수 : 7개

- 간선의 수 : 6개

- 1번 컴퓨터를 통해 바이러스 걸리는 컴퓨터 수 : 4개

---

✏️문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Baek2606 {

    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int N, M, count;

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

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

        visited = new boolean[N+1];
        for(int i=0; i<N+1; i++){
            graph.add(new ArrayList<>());
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            graph.get(x).add(y);
            graph.get(y).add(x);
        }

        DFS(1) or BFS(1);
        System.out.println(count);
    }
}

 

BFS

    private static void BFS(int v){
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(v);
        visited[v] = true;

        while(!queue.isEmpty()){
            int node = queue.poll();
            for(int i=0; i<graph.get(node).size(); i++){
                int temp = graph.get(node).get(i);
                if(!visited[temp]) {
                    visited[temp] = true;
                    queue.offer(temp);
                    count++;
                }
            }
        }
    }

 

DFS

    private static void DFS(int v){
        if(!visited[v]){
            visited[v] = true;
        }

        for(int i=0; i<graph.get(v).size(); i++){
            int node = graph.get(v).get(i);
            if(!visited[node]){
                DFS(node);
                count++;
            }
        }
    }

---

💡새로 알게된 점

2중 리스트를 사용할 때

static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

 

여기에 값을 넣기 전에 이 리스트를 초기화 해야된다는 걸 알았다!!

 

for(int i=0; i<N+1; i++){
    graph.add(new ArrayList<>());
}

---