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

# 2606 바이러스

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

2606번: 바이러스

코드

N = int(input())
C = int(input())

graph = [[] for i in range(N+1)]
visited = [0] * (N+1)

for i in range(C):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

def dfs(M):
  visited[M] = 1
  for nx in graph[M]:
    if visited[nx] == 0:
      dfs(nx)

dfs(1)
print(sum(visited)-1)

📝 풀이

DFS(깊이우선탐색)와 BFS(너비우선탐색)로 풀 수 있는 문제이다. DFS는 깊이 우선 탐색으로, 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다. DFS는 맹목적으로 각 노드를 탐색할 때 주로 사용된다. BFS에서는 큐가 사용되었다면 DFS에서는 스택이 사용된다.

DFS는 다음과 같은 알고리즘에 따라 작동한다.

1. 스택의 최상단 노드를 확인

2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺀다.

 

위 알고리즘을 계속해서 반복 수행하면 된다.

 

📝 코드 뜯어보기

N = int(input()) # 컴퓨터의 수
C = int(input()) # 연결된 컴퓨터 쌍의 수

graph = [[] for i in range(N+1)] # 연결된 컴퓨터 쌍의 수만큼 반복 [[], [], [], [], [], [], [], []]
visited = [0] * (N+1) # 방문처리 [0, 0, 0, 0, 0, 0, 0, 0]

for i in range(C): # 연결된 컴퓨터 쌍의 수만큼 반복
  a, b = map(int, input().split())
  graph[a].append(b) # 양쪽을 연결
  graph[b].append(a) # [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]

1. 연결된 컴퓨터 쌍의 수만큼 graph를 생성하고 방문처리를 위한 visited를 만들어준다.

2. 연결된 컴퓨터 쌍의 수만큼 반복문을 실행시켜주고 graph에 a,b 양쪽 노드를 연결시켜준다.

3. 방문한 visited 값을 더해준다.

def dfs(M):
  visited[M] = 1
  for nx in graph[M]: # [2, 5] or [1, 3, 5] or [1, 2, 6] 등
    if visited[nx] == 0:
      dfs(nx)

dfs(1)
print(sum(visited)-1)

dfs함수를 선언해주고 M을 입력받게 되면 visited에 방문처리를 해준다. graph[M]을 반복문을 통해 visited[nx]가 방문하지 않은 곳이라면 dfs함수를 재실행시켜준다.

 

dfs(1)이 바이러스에 걸린 컴퓨터라면 dfs함수가 실행되면서 연결된 노드를 방문처리하게 되고 방문한 컴퓨터 개수 - 1번 컴퓨터를 print해주면 정답이 된다.