2606: 바이러스 - Python

문제

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

그래프 관련 문제를 풀어본 적이 없어서, codingDNA님의 코드를 참고했다.

풀이 1 (BFS)

from collections import deque # BFS는 deque로 구현

n = int(input()) # node
e = int(input()) # edge
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)

for _ in range(e): # graph 생성
    a, b = map(int, input().split())
    graph[a] += [b] # 양방향 연결
    graph[b] += [a]


# BFS
visited[1] = 1
Q = deque([1])
while Q:
    current = Q.popleft()
    for next in graph[current]:
        if visited[next] == 0:
            Q.append(next)
            visited[next] = 1

print(sum(visited) - 1) # 1번 컴퓨터 제외

풀이 2 (DFS)

# 공통
n = int(input())
e = int(input())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)

for _ in range(e):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]


# DFS
def dfs(current): # dfs는 함수를 정의해서
    visited[current] = 1
    for next in graph[current]:
        if visited[next] == 0:
            dfs(next) # 다음 노드를 재귀적으로 호출
            
dfs(1) # 1번 컴퓨터에서 시작
print(sum(visited) - 1)

---

오늘의 교훈

• BFS는 Queue를 이용해 구현한다.
  특히 deque와 .popleft()를 이용한다.
• DFS는 재귀 함수 혹은 Stack을 이용해 구현한다.
• list[a] += [b]는 list[a].append(b) 혹은 list[a].extend([b])와 같은 동작을 수행한다.

참고 자료

• [백준] 2606 바이러스 - Python (그래프 탐색)
• [자료구조] BFS, DFS 총정리