BOJ 2606. 바이러스 (Python)

BOJ 2606. 바이러스

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

2606번: 바이러스

풀이

DFS를 통해 탐색한 노드의 수 - 1 (1번 컴퓨터는 제외) 를 구해주면 된다.
틀렸습니다 를 굉장히 많이 봤는데 이유는 그래프를 단방향으로 만들어 주어서 이다. 테스트 케이스에선 잘 나와서 생각하지 못했다.
앞으로 방향 을 언급하지 않으면 양방향으로 해 주어야 하는것을 잊으면 안되겠다.
재귀로도 풀 수 있다.

• dfs 파이썬 구현

소스코드

import sys
from collections import defaultdict

N = int(input()) # 노드(컴퓨터) 수
M = int(input()) # 간선(컴퓨터 쌍)의 수

computer = defaultdict(list)

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    computer[a].append(b)
    computer[b].append(a)

discoverd = []
stack = [1]

# DFS
while stack:
    v = stack.pop()
    if v not in discoverd:
        discoverd.append(v)
        for w in computer[v]:
            stack.append(w)

print(len(discoverd) - 1)

예외처리를 하나 안하나 속도는 같았다.