BOJ 2606 바이러스 python

기

이 문제는 dfs 혹은 bfs로 그래프를 순회하면서 1번과 연결돼있는 노드의 수를 카운트 하는 기본적인 그래프 탐색 문제이다.

승

우선 인접 리스트로 그래프를 만들고, bfs를 이용해서 연결된 노드들을 찾아냈다. dfs를 사용하면 구현은 더 간단하겠지만 시스템 상의 스택이 허용하는 범위에서의 탐색만 가능하다는 한계가 명확하기에, bfs로 구현하려고 했다.

전

그래프를 만들 때, 인접 노드를 오름차순으로 탐색하므로 정렬을 해주었다.

1. 큐의 모든 원소가 사라질 때 까지 맨 앞 노드를 pop한다.

2. 그 노드의 미방문 인접 노드들을 방문 처리한다.

3. 방문 처리한 노드들에 대해 원하는 동작을 구현한다 -> 여기서는 cnt를 1 증가시킨다.

4. 방문 처리한 노드들을 다시 큐에 집어넣는다.

이 동작이 끝나고 나면 하나의 그래프에서 bfs가 완료된다.

 

결

문제의 의도가 명확한, 그래프 탐색 연습용으로 정말 좋은 문제였다.

---

코드

from collections import deque

com = int(input())
edge = int(input())

graph = [[] for _ in range(com+1)]
visited = [False] * (com+1)

for _ in range(edge):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)
    graph[s].sort()
    graph[e].sort()

q = deque([1])
cnt = 0

while q:
    v = q.popleft()
    visited[v] = True
    for child in graph[v]:
        if not visited[child]:
            visited[child] = True
            q.append(child)
            cnt += 1

print(cnt)