(Python) DFS (깊이 우선 탐색) 백준 2606번(재귀함수 제한 해제)

---

DFS (깊이 우선 탐색)

한 노드와 연결된 모든 부분 먼저 탐색하는 BFS와 달리 
DFS는 먼저 한 부분을 최대한 깊숙이 확인하고 돌아와 다른 부분을 탐색하는 것이다.  

재귀호출이나 스택 배열을 이용하여 구현한다.

---

2606번 바이러스

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

트리 형태 문제이며 dfs 기본 문제라고 할 수 있다.
 
연결되어 있는 컴퓨터 종류 알려준다.
바이러스가 감염되면 연결되어 있는 컴퓨터도 감염된다.
1번 컴퓨터가 감염됐을 때 감염되는 컴퓨터의 수를 출력하는 문제이다.
 
DFS로 생각하면 1의 경우가 되는 부분만 탐색하면 된다.
 
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
 
1. 입력받은 컴퓨터 연결을 순서대로 정리해서 리스트에 저장한다.
2. 저장된 리스트를 재귀를 통해 DFS로 푼다.
 
이 코드가 완벽한 정답이라고는 볼 수 없지만 이렇게 풀 수 있다.

import sys # 입력이 많을 때 사용(시간초과 방지)

n = int(input())
link = int(input())

array = []
array.append(0) # 문제에서 컴퓨터 번호가 1부터 있기에 0번째 위치를 미리 채운다. 사용 X
for i in range(link):
  array.append(list(map(int, sys.stdin.readline().split())))
  
graph = [[] for _ in range(n + 1)] # 1부터 n까지 사용하기 때문에 n + 1 

for j in range(1, link + 1): # 연결된 컴퓨터들을 번호대로 넣어준다.
  graph[array[j][0]].append(array[j][1])
  graph[array[j][1]].append(array[j][0])
  
def dfs(graph, v, visited): # 매개변수 v는 시작 위치인 1이다.
  visited[v] = True # 방문처리
  for i in graph[v]:
    if not visited[i]: # 방문 안했으면 dfs 함수로 방문 처리
      dfs(graph, i, visited)
      
visited = [False] * (n + 1) # 컴퓨터 갯수만큼 
dfs(graph, 1, visited)

print(visited.count(True) - 1) # 방문처리된 컴퓨터 갯수 1번 컴퓨터를 제외해야하기에 -1

리스트로 방문 사실만 해주면 된다.
재귀를 이용하는 것은 방문처리만 해주는 것이라 코드가 간단하다.
 
다른 문제를 풀다보면 파이썬 재귀 횟수가 제한되어 있어
import sys
sys.setrecursionlimit(재귀 횟수)
위 코드를 코드 위에 넣어주면 된다. 
재귀 횟수는 10**6을 많이 넣는다.