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

안녕하세요 놀이방 사장입니다.

 

이번 포스팅은 백준 2606

"바이러스" 문제 풀이 포스팅입니다.

 

기본적인 DFS 문제 같습니다.

근데 양방향으로 해주어야 합니다.

처음에 단방향으로 풀었다고 계속 틀렸다고 해서 혹시나 양방향으로 그래프를 그리니깐

바로 정답처리되더라구요..

 

이번 문제는 1번 컴퓨터를 기준으로 바이러스가 전염되는 컴퓨터의 갯수를 구하는 문제입니다.

dfs나 bfs 둘 중에 하나로 풀면 될 거 같네요

 

저는 dfs로 풀었습니다.

 

그래프는 ArrayList를 이용해서 만들어주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
    public static boolean[] computers;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    public static int count = 0;

    public static void getDfs(int x){
        computers[x] = true;
        count++;
        for(int i=0; i<graph.get(x).size(); i++){
            int y = graph.get(x).get(i);
            if(!computers[y]){
                getDfs(y);
            }
        }
    }

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        computers = new boolean[n];
        for(int i=0; i<n; i++){
            graph.add(new ArrayList<Integer>());
        };
        for(int i=0; i<m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            graph.get(a).add(b);
            graph.get(b).add(a);
        };
        getDfs(0); //1번컴퓨터는 이미 감염되어있기 때문에
        System.out.println(count-1);
    }
}

 

밑에 코드가 그래프를 만들어주는 코드입니다.

먼저 n을 받아서 노드 갯수를 추가해줍니다.

테스트 케이스 기준 7개

그 후 노드들을 연결해줍니다.

6개 

양방향이기에 둘 다 추가해줘야합니다.

 

graph.get(a).add(b);
graph.get(b).add(a);

 

public static void getDfs(int x){
    computers[x] = true;
    count++;
    for(int i=0; i<graph.get(x).size(); i++){
        int y = graph.get(x).get(i);
        if(!computers[y]){
            getDfs(y);
        }
    }
}

 

1번 컴퓨터부터 연결된 노드를 차례대로 너비탐색하면서 가주면 됩니다.

false = 방문하지 않은 노드

true = 방문한 노드

방문한 노드는 무시하면서 탐색하면 됩니다.

 

마지막 -1은 1번 컴퓨터는 제외시켜야 하기 떄문입니다.

 

감사합니다!