[BOJ] 2606 : 바이러스 [그래프탐색](Python)

문제 링크

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

2606번: 바이러스

소스 코드

from collections import deque

c = int(input())
graph = [[] for _ in range(c+1)]

n = int(input())
for i in range(n):
    # 양방향 간선 추가
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

# 이 문제에서는 정렬 불필요해보임
graph = [sorted(x) for x in graph]
visited = [0 for _ in range(c+1)]

def bfs(start):
    visited[start] = 1 # 시작노드 방문처리
    queue = deque([start])

    while queue:
        cur = queue.popleft() # 현재 노드
        for next in graph[cur]: # 이동 가능 노드
            if not visited[next]: # 방문하지 않았다면
                visited[next] = 1 # 방문 처리
                queue.append(next) # 큐에 추가

bfs(1)
print(visited.count(1)-1) # 1(방문처리)인 노드개수 - 1

 

해설

• 그래프 탐색, BFS
• 양방향 간선

그래프 탐색에 대한 개념이 있다면 간단히 풀 수 있는 문제였습니다.

 

1) 그래프 입력 받기, 방문 여부 리스트 초기화

두 작업을 수행할 때는 노드 번호를 곧 인덱스로 사용하기 때문에 범위를 총 컴퓨터의 개수 c보다 1 큰 값으로 정합니다.

예를 들어 1번 컴퓨터는 graph[1] 로 접근할 수 있게 하는 것입니다.

 

2) bfs 함수 정의

collections 라이브러리의 deque 를 사용합니다.

deque는 선입선출(FIFO) 방식에 적합한 자료구조입니다.

시작 노드인 1에서 출발하여 이동 가능한 노드들을 queue에 추가합니다.

여기서 이동 가능하다는 것은 이전에 방문한적이 없어 visited 리스트에서 -1의 값을 갖는 노드라는 뜻입니다.

 

3) 방문 처리 노드 개수 - 1을 출력

시작 노드인 1을 기준으로 몇 개의 컴퓨터가 감염되었는지 세는 것이므로 1번 자체는 포함하지 않습니다.

따라서 visited에 1인 값들의 개수에서 1을 뺀 값이 정답이 됩니다.