[백준] 바이러스 -재 풀이

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

 

 

 

문제 파악

-컴퓨터가 이어져있으면 바이러스가 옮는다. 는 개념

-저번에 파이썬으로 푼 문제 재풀이

-한 네트워크에서 영향받는 컴퓨터 수 세는 것임

 

접근 방법

-주어진 int끼리 연결하여 인접 리스트 먼저 만들고(양방향)

해당 노드와 이어진 모든 노드 순회하며 카운트

-visited와 count는 모두 멤버변수로 선언한다.

 

코드 구현

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

public class 바이러스 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] visited;
    static int count;

    public static void main(String[] args) throws IOException {
        int computer = Integer.parseInt(br.readLine());
        int connected = Integer.parseInt(br.readLine());
        visited = new int[computer+1];
        for (int i=0;i<computer+1;i++){
            graph.add(new ArrayList<>());
        }
        for (int i=0;i<connected;i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            graph.get(s).add(e);
            graph.get(e).add(s);
        }

        count = 0;
        DFS(1);
        System.out.println(count);
    }

    private static void DFS(int start) {
        visited[start] += 1;
        for (int i=0;i<graph.get(start).size();i++){
            int v = graph.get(start).get(i);

            if(visited[v]==0){
                count++;
                DFS(v);
            }

        }
    }
}

 

 

배우게 된 점

프로그래머스의 <네트워크>와 이름이 같은 문제인데,

이 문제는 네트워크 내 컴퓨터 갯수를 세는 것이고

프로그래머스 문제는 네트워크의 갯수를 세는 것이라 좀 성격이 다르다.

 

좌) DFS - 네트워크 한번 / 우) DFS - 네트워크 여러번

 

DFS문제 중 사방을 체크하며 후보들을 큐에 담거나, 발견되는 대로 즉시 순회하는 경우가 있는데
이 경우도 dfs를 여러 번 한다고 봐야 한다. 

여러 방향으로 타고 타고.. 그니까 타고 타고, 를 한번하는지, 아니면 여러번 하는지를 보면 됨.

여러번 하는 경우 dfs가 모두 끝나서 순회를 마치고 돌아와도, 다른 경우의 수를 탐색해야 하므로

처음 dfs를 돌 때부터 반복문을 줘야 한다.

 

헷갈리는 부분이라 비교해봄..

 

 

끝