백준 - 2606 바이러스 [DFS] 자바 백준 1위

 

2606번: 바이러스

 

1. 문제 요약

컴퓨터의 수 n, 직접 연결된 컴퓨터의 수 m, 연결된 컴퓨터 쌍의 번호가 주어진다.

1번 컴퓨터와 직간접적으로 연결되어 있는 컴퓨터의 수를 구하시오.

2. 접근 방법

DFS(깊이 우선 탐색) 알고리즘을 사용합니다.

• 1번을 기준으로 찾으면 되기 때문에, 4번과 7번은 무시합니다.
• 1번에서 2번을 방문하고, 2번은 방문했다고 표시를 합니다.
• 2번에서 방문할 수 있는 곳들 중 방문하지 않은 곳을 방문합니다.
• 3번으로 방문 후, 더 이상 방문할 곳이 없으므로 2번으로 돌아갑니다.
• 2번에서 방문할 수 있는 곳 중 방문하지 않은 곳은 5번이므로 5번으로 이동합니다.
• 5번에서 방문할 수 있는 곳 중 방문하지 않은 곳은 6번이므로 6번으로 이동합니다.
• 6번을 방문 후 더 이상 방문할 곳이 없으므로 종료합니다.

 

3. 파이썬

from sys import stdin
input = stdin.readline

def solution(idx:int):
    if not virus[idx]:
        global answer
        virus[idx] = True
        answer += 1
        for i in network[idx]:
            solution(i)

n = int(input())
m = int(input())
network = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    network[a].append(b)
    network[b].append(a)

virus = [False] * (n+1)
answer = -1

solution(1)
print(answer)

 

4. 자바

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        n = read();
        m = read();
        virus = new boolean[n + 1];
        for (int i = 0; i < m; i++) {
            int a = read();
            int b = read();

            List<Integer> aOrDefault = network.getOrDefault(a, new ArrayList<>());
            aOrDefault.add(b);
            network.put(a, aOrDefault);

            List<Integer> bOrDefault = network.getOrDefault(b, new ArrayList<>());
            bOrDefault.add(a);
            network.put(b, bOrDefault);
        }

        solution(1);
        System.out.println(answer);
    }

    static int n, m;
    static int answer = -1;
    static boolean[] virus;
    static Map<Integer, List<Integer>> network = new HashMap<>();

    private static void solution(int key) {
        if (virus[key]) {
            return;
        }
        virus[key] = true;
        answer += 1;

        if (network.get(key) != null) {
            for (Integer computer : network.get(key)) {
                solution(computer);
            }
        }
    }

    // 읽기
    private static int read() throws Exception {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/2606.%E2%80%85%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4