[Python/백준] 2606. 바이러스

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

더보기

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

---

풀이

import sys
input = sys.stdin.readline

# 그래프 탐색 알고리즘 기본 문제.

n = int(input())
m = int(input())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)

def dfs(node):
    # 2. 재귀하며 현재 정점 action 실행
    global counts
    counts += 1

    # 3. 인접한 모든 정점들에 대해
    for next_node in graph[node]:
        # 4. 방문x 인접 노드 이동(함수 호출)
        if not visited[next_node]:
            visited[next_node] = True
            dfs(next_node)

visited = [False] * (n + 1)
counts = 0

# 1. 시작 정점 방문 처리
visited[1] = True
dfs(1)
print(counts - 1)