백준 2606번: 바이러스 (S3) - Python 풀이

이번 주차는 DFS/BFS입니다. DP 말고 차라리 이걸 저번 주에 하는 게 나았을지도...
유형은 너무 익숙하지만 맨날 까먹어서 (머릿속에 남아 있는 건 visited 뿐) 이번엔 꼭 정복해 보겠습니다.
 

문제 설명

https://www.acmicpc.net/problem/2606
 
하나의 컴이 바이러스에 걸리면 네트워크 상 그 컴과 연결된 모든 컴이 바이러스에 걸리게 된다.
1번 컴을 통해 바이러스에 걸리게 되는 컴의 수를 출력해야 한다. -> 1번 컴은 제외된다.

• 입력
  • 컴퓨터의 수 N (0 < N <= 100)
  • 네트워크 상에서 연결되어 있는 컴퓨터 쌍의 수 M
  • 한 쌍씩 연결돼 있는 컴퓨터 번호 쌍 u, v

풀이 과정

N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]

# 감염된 컴퓨터 목록
virused_computers = []

for _ in range(M):
    # 정점 인풋
    u, v = map(int, input().split())
    # 서로 각 인덱스에 값을 추가
    graph[u].append(v)
    graph[v].append(u)

# 정점 방문 여부를 저장하기 위한 배열
visited = [False for _ in range(N+1)]

# 깊이 우선 탐색! start 위치에 있는 정점에서 시작
def dfs(start, graph, visited):
    # 방문한 걸로 변경
    visited[start] = True
    # start번 컴퓨터와 연결돼 있는 이웃 컴퓨터들을 for 문으로 순회
    for neighbor in graph[start]:
    	# (바이러스가) 아직 방문을 안 했다면
        if not visited[neighbor]:
            # 너 이제 감염된 컴퓨터
            virused_computers.append(neighbor)
            # dfs에 start를 neighbor로 넣어서 방문
            dfs(neighbor, graph, visited)
            
# 바이러스 방문의 시작은 1번 컴퓨터
dfs(1, graph, visited)

# 감염된 컴퓨터의 총 개수
print(len(virused_computers))

 
DFS 알고리즘을 공부하여 풀었다. 코드 설명은 주석으로 대체.
 
 
+ 이거 BFS로 풀어도 풀릴 것 같아서 해봤다.
 
BFS는 가까운 노드부터 탐색해야 한다. 그래서 탐색 순서가 중요하고, 먼저 방문하는 노드를 먼저 처리해야 하기 때문에 구현 시 FIFO 구조인 큐를 사용해야 한다.
 
이 문제는 연결된 모든 노드를 방문하는 것이 목적인 문제이기 때문에, 그래프의 '탐색 방식'이 결과에 영향을 주지 않는다. 두 방식의 차이는 그냥 탐색 순서다.

from collections import deque # pop의 최적화를 위해 deque 사용

N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]
virused_computers = []

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

visited = [False for _ in range(N+1)] # 여기까지 dfs와 동일

def bfs(start, graph, visited):
    queue = deque([start]) # start번 컴퓨터를 담은 큐 생성
    visited[start] = True # 방문으로 변경
    
    # queue에 값이 들어있다면 반복
    while queue:
    	# 큐(FIFO)에서 맨 앞의 값을 pop
        computer = queue.popleft()
        # 해당 컴퓨터의 이웃들을 for 문을 통해 순회
        for neighbor in graph[computer]:
            # 아직 방문되지 않았던 컴퓨터라면
            if not visited[neighbor]:
                # 큐에 추가
                queue.append(neighbor)
            	# 방문으로 변경
                visited[neighbor] = True
                # 감염된 컴퓨터로 추가
                virused_computers.append(neighbor)

bfs(1, graph, visited)

print(len(virused_computers))