[백준 2606번: 바이러스] 파이썬 풀이 _ 깊이 우선 탐색(DFS)

2606번: 바이러스

---

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

---

풀이

import sys

input = sys.stdin.readline

n = int(input())  # 컴퓨터의 수 n
m = int(input()) # 연결된 컴퓨터 쌍의 수 m
li = [[] for _ in range(n + 1)] # 정점 간 연결 정보를 입력받을 리스트 li
visited = [False] * (n + 1) # 방문 여부를 표시할 리스트

# 정점 간 연결 정보 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    li[a].append(b)
    li[b].append(a)

 #재귀함수로 dfs 구현
def dfs(v):
  visited[v] = True 
  for i in li[v]:
    if not visited[i]:
      dfs(i)

dfs(1)
print(visited.count(True)-1) 
#1번 컴퓨터는 카운트에서 제외하므로 1을 빼고 True로 바뀐 개수를 출력함

 

재귀함수를 이용한 dfs로 풀이하였습니다.

 

---

정점 간 연결 정보 입력받기

# 정점 간 연결 정보 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    li[a].append(b)
    li[b].append(a)

 

• li(정점 간 연결 정보) 리스트는 아래 예시와 같이, 1번 인덱스에는 정점 1과 연결된 정점을, 2번 인덱스에는 정점 2와 연결된 정점을 리스트 형태로 표현하도록 입력받았습니다.
• 인덱스 번호와 리스트를 맞추었기 때문에 0번 인덱스는 빈 배열입니다.

li = [
    [],       # 더미(dummy) 값
    [2, 3, 4],  # 정점 1과 연결된 정점들: 2, 3, 4
    [4],       # 정점 2와 연결된 정점: 4
    [4],       # 정점 3과 연결된 정점: 4
    []        # 정점 4와 연결된 정점들: (없음, 고립된 정점)
]

재귀함수로 dfs 구현

#재귀함수로 dfs 구현
def dfs(v):
  visited[v] = True 
  for i in li[v]:
    if not visited[i]:
      dfs(i)

 

• dfs라는 함수를 정의하였고, 하나의 정점을 확인할 때 마다 visited 배열을 True로 바꾸면서 방문 여부를 표시했습니다.
• 현재 보고 있는 정점과 연결된 정점을 for문을 돌며 모두 확인하면서, 방문하지 않았다면 재귀함수를 통해 연결된 정점을 방문하는 형태로 dfs를 구현했습니다.

결과 출력

dfs(1)
print(visited.count(True)-1) 
#1번 컴퓨터는 카운트에서 제외하므로 1을 빼고 True로 바뀐 개수를 출력함

 

1번 컴퓨터가 바이러스에 걸렸으므로 무조건 시작 지점은 1이기 때문에 dfs(1)을 해주고,

visited에서 True로 바뀐 곳만 방문, 즉 바이러스에 걸렸으므로 True를 카운트해주었습니다.

 

단, 1번 컴퓨터는 세지 않으므로 1번 컴퓨터를 제외한 개수를 count해서 출력합니다.

 

---

깊이 우선 탐색(DFS)란?

• 깊이 우선 탐색(DFS) 그래프나 트리 구조에서 모든 노드를 방문하고자 할 때 사용되는 탐색 알고리즘
• DFS는 한 지점에서 시작하여 다음 지점으로 이동할 때 최대한 깊숙히 들어가서 더 이상 갈 곳이 없을 때까지 탐색하고, 그 후에 백트래킹하여 다른 가능한 경로를 탐색한다. 이를 재귀 함수나 스택을 활용하여 구현할 수 있다.

DFS의 주요 특징

1. 스택 또는 재귀 함수를 사용하여 구현
2. 한 노드에서 가능한 한 깊게 들어가서 다음 노드를 탐색
3. 깊은 경로를 탐색한 후에는 백트래킹을 통해 다른 경로를 시도

파이썬에서의 DFS 구현 예제

• 그래프를 인접 리스트로 표현하고 DFS를 사용하여 그래프를 탐색

# 그래프를 인접 리스트로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = {}  # 방문 여부를 저장할 딕셔너리

def dfs(node):
    if node not in visited:
        print(node, end=' ')  # 노드를 방문한 것으로 표시하고 출력
        visited[node] = True
        for neighbor in graph[node]:
            dfs(neighbor)  # 이웃 노드를 재귀적으로 방문

# 시작 노드 'A'에서 DFS 시작
dfs('A')

 

이 코드는 'A' 노드에서 시작하여 DFS로 그래프를 탐색한다. 방문한 노드를 출력하고 방문 여부를 딕셔너리로 관리하여 무한 루프를 방지한다.