백준 2606번: 바이러스 [python]

난이도 : 실버 3
유형 :
https://www.acmicpc.net/problem/2606

문제 접근

노드와 간선으로 이루어져있는 무방향 그래프가 보인다.
시작 노드가 주어지고, 전체 순회했을 때 순회한 노드의 수를 출력하는 문제
-> DFS 나 BFS 로 구현하면 될 것 같다.

두 방식 다 큰 무리 없이 가능하지만
"단순 연결된 개수 세기" → DFS가 살짝 더 직관적인 것 같아 DFS로 풀겠다.

DFS 구현 절차는 다음과 같다.
1. 입력받기
2. 그래프 구현하기.
3. 방문 리스트 선언하기.
4. 인접노드 방문 순서 필요하다면 정렬하기
5. DFS 함수 정의
6. DFS(시작노드)
7. 출력

해답 및 풀이

import sys
input = sys.stdin.readline

# 1. 입력 받기
N = int(input()) # 컴퓨터의 수
M = int(input()) # 간선의 수

edges = []

for _ in range(M):
    u,v = map(int,input().split())
    edges.append((u,v))

# 2. 그래프 구현
graph = []
for _ in range(N+1):
    graph.append([])

for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

# 3. 방문 리스트 선언하기
visited = [False] * (N+1)

# 4. 인접노드 방문 순서 정렬 필요하지 않아 생략

# 5. DFS 함수 정의
cnt = 0
def DFS(node):
    global cnt
    visited[node] = True
    cnt += 1

    for neighbor in graph[node]:
        if visited[neighbor] == False:
            DFS(neighbor)


DFS(1)
print(cnt-1) # 1번 컴퓨터가 감염시킨 컴퓨터의 수이기 때문에 1번 컴퓨터는 제외해야하여 -1 처리