Codeup 4503 BaekJoon 2606 바이러스 DFS

  Ex) 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

  - 신종 바이러스가 네트워크를 통해 전파된다.  한 컴퓨터가 바이러스에 걸리면 그  컴퓨터와 네트워크 상에서 연결된 모든 컴퓨터는 바이러스에 걸리게 된다. 

  - 첫째 줄에는 컴퓨터의 수가 주어진다.

  - 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 순서쌍의 수, 셋째 줄에는 순서쌍이 나열되어있다.

<hide/>
import java.util.*;
public class Virus {

    static int MAX_COUNT = 101;
    static int[][] AdjMat = new int[MAX_COUNT][MAX_COUNT];
    static int[] Visited = new int[MAX_COUNT];
    static int numOfNode = 0;
    static int numOfEdge = 0;
    static int result = 0;
    static int startNode = 0;
    
    public static void DFS(int _node){

        Visited[_node] = 1;
        for(int i = 1; i <= numOfNode; ++i) {
            if (Visited[i] == 0 && AdjMat[_node][i] == 1) {
                ++result;
                int nextNode = i;
                System.out.println("curr: " + _node + ", next: " + i + ", result: " + result);
                DFS(nextNode);
            }
        }
    }

    public static void main(String[] args){

        Scanner scan = new Scanner(System.in);
        numOfNode = scan.nextInt();
        numOfEdge = scan.nextInt();

        for(int i = 0; i < numOfEdge; ++i){
            int x = scan.nextInt();
            int y = scan.nextInt();
            AdjMat[x][y] = 1;
            AdjMat[y][x] = 1;
        }
        startNode = 1;
        DFS(startNode);
        System.out.println(result);
    }
}

   Note) 입출력 예시

<hide/>
[입력]
7 6

[출력]
1 2
2 3
1 5
5 2
5 6
4 7

  - DFS는 BFS와 다르게 재귀함수를 사용한다.

  - 비교적 간단한 1차원 행렬이고 단방향 그래프라서 간단하게 구현할 수 있다.

  - Visited: 1차원 행렬로 방문했는지 여부를 1(true) / 0(false)로 구분한다.

  - 인접행렬과 방문행렬 모두 index를 1부터 사용한다.

 

출처

https://codeup.kr/problem.php?id=4503&rid=0 

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