백준 2606 - 바이러스 (JAVA 자바)

백준 2606 - 바이러스 (JAVA 자바)

www.acmicpc.net/problem/2606

2606번: 바이러스

 

DFS의 가장 기본이 되는 문제 같습니다. 

 

풀이방법은 아래의 사항들을 참고하여 풀어주시면 됩니다.

 

1. 시작지점은 무조건 1번 컴퓨터에서부터 시작되므로, 

   1번에서 연결된 컴퓨터들만 모두 돌면서 wasted 변수를 증가시켜준다.

2. 한번 방문한 지점은 방문체크를 해주고, 다시 방문 안하도록 해준다. 

3. 간선으로 연결되어 있는 곳은 DFS를 돌려주고, 

    DFS를 돌기 전에 (감염된 컴퓨터의 갯수를 세야 하므로)

    wasted 함수를 1 증가 시켜준다. 

4. 마지막에 wasted변수를 출력해주면 정답이 된다.

 

 

 

import java.util.*;
 
public class Baekjoon_virus {
    
    static int computers,networks,wasted;
    static boolean visits[];
    static boolean map[][];
    
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        
        computers = sc.nextInt();
        networks = sc.nextInt();
        visits = new boolean [computers+1];
        map = new boolean [computers+1][computers+1];
        wasted = 0;
        
        for (int i=1; i<=networks; i++) {
            int tmp1 = sc.nextInt();
            int tmp2 = sc.nextInt();
            
            map[tmp1][tmp2] = true;
            map[tmp2][tmp1] = true;
            
        }
        
        dfs(1);
        
        System.out.println(wasted);
        
    }
 
    private static void dfs(int start) {
        visits[start] = true;
        for(int i=1; i<=computers; i++) {
            if(map[start][i] && !visits[i]) {
                wasted++;
                dfs(i);
            }
        }
    }
}