[백준/S3/DFS/자바] 2606 바이러스

💡 문제

 

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면

그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자.

1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번

컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다.

하지만 4번과 7번 컴퓨터는1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

 

 

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다.

컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가주어질 때,

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

⌨ 입력 

 

첫째줄 : 컴퓨터의수 ( n <= 100 ) 각 컴퓨터는 1번 부터 차례대로 번호가 매겨진다.

둘째줄 : 연결 되어 있는 컴퓨터의 수

셋째줄 : 연결 된 컴퓨터 번호의 쌍 

 

 

💻 출력 / 제한

 

1번 컴퓨터가 웜 바이러스에 걸렸을때 ,

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력

 

---

 

풀이 방법 

 

연결 정보를 담기위해 2차원 배열 혹은 ArrayList<<ArrayList<Integer>>가 필요합니다.

 

 

 

각 ArrrayList의 행은 해당 컴퓨터의 번호를 의미하고,

값은 컴퓨터와 연결된 다른 컴퓨터들을 의미한다.

컴퓨터의 수 + 1 만큼의 ArrayList를 만들어 값을 넣습니다.

 

( 컴퓨터의 수 : 5  >  0 ~ 5 까지의 컴퓨터가 필요하므로 )

번호가 0인 컴퓨터는  없으므로 비워 둡니다.

 

해당 컴퓨터에 접근 했는지 확인 하기위해 boolean[] visited 배열을 사용합니다.

 

 

 

dfs를 호출 하는법은 1번 컴퓨터만 dfs를 실행해서 바이러스 감염여부를 확인하면 됩니다.

 

 

 

dfs의 재귀 호출 방식은 예시를 들어 설명 하겠습니다.

 

 

dfs(1) 을 호출 합니다. 

1번째 인덱스의 List를 얻어 방문 체크  >  dfs(2), dfs(5) 호출

dfs(2) 을 호출 합니다.

현재 컴퓨터 방문 체크합니다. List를 얻고 다른 컴퓨터 방문 체크  >  1번 체크(o) /  dfs(3), dfs(5) 호출

dfs(3) 을  호출 합니다.

현재 컴퓨터 방문 체크합니다. List를 얻고 다른 컴퓨터 방문 체크  > 2번 체크(o) / 거슬러 올라갑니다.

dfs(5) 을 호출합니다.

현재 컴퓨터 방문 체크합니다. L ist를 얻고 다른 컴퓨터 방문 체크  > 1,2 체크(o) / dfs(6) 호출

dfs(6) 을 호출합니다.

현재 컴퓨터 방문 체크합니다. List를 얻고 다른 컴퓨터 방문 체크 > 5 체크(o) / 거슬러 올라갑니다.

 

이러한 방식으로 깊이 우선 탐색을 하며 재귀 호출을 합니다.

1번 컴퓨터와 연관된 모든 컴퓨터를 방문 체크 하게 됩니다.

답은 1번 컴퓨터와 연결된 수이므로 visited[] 배열에서 값을 구하고 -1 하면 됩니다.

 

💥 느낀점

 

DFS / BFS 너무 어렵습니다. ㅠㅠ

N-queen 골드4 dfs 문제를 풀다가 DFS 개념이 부족 한 것 같아 유튜브 동빈나 DFS/BFS 듣고

조금 씩 난이도를 높은 문제를 풀려고 합니다.

 

전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.stream.Stream;

public class Virus2606 {
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int computerNum = Integer.parseInt(br.readLine());
        int connectNum = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        visited = new boolean[computerNum + 1];

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

        for(int i=0; i<connectNum; i++){
            int[] input = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            list.get(input[0]).add(input[1]);
            list.get(input[1]).add(input[0]);
        }

//        int index = 0;
//        for (ArrayList<Integer> integers : list) {
//
//            System.out.print(index + "번째 인덱스 : ");
//
//            for (Integer i : integers) {
//                System.out.print(i);
//            }
//            index++;
//            System.out.println();
//        }

        dfs(1);

        int virusNum = 0;
        for (boolean visited : visited) {
            if(visited) virusNum++;
        }

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

    static void dfs(int index){

        if(!visited[index]){
            visited[index] = true;
//            System.out.println(index + "에 방문 했습니다.");
            ArrayList<Integer> rowList = list.get(index);

            for (int i : rowList) {
                if(!visited[i]) dfs(i);
            }
        }

    }
}