문제
파이썬으로 DFS, BFS 연습을 제대로 한 적이 없어서 이참에 제대로 시작할 예정입니다. (지난주에 본 코테에서 간단한 DFS를 한참을 잡고 있었던 슬픈 기억이ㅠㅠ)
네이버블로그에서 기술블로그 활동을 할 때에 DFS/BFS 감을 익혔던 문제 순서대로 문제를 다시 풀고, 해설을 업로드 하려고 합니다!
해설
start node가 주어질 때, 해당 노드와 연결된 노드의 수를 구하는 문제입니다. DFS, BFS 둘 중 무엇으로 풀어도 상관없습니다. 단, 연결된 노드의 수를 구하는 문제이므로 start node의 수는 제외합니다.
# start==1가 주어질 때 연결된 노드의 수를 구하라 (start는 제외한다)
# nodeList에 양방향으로 노드를 연결해주는 함수입니다.
def addNode(first, second, nodeList) :
if first in nodeList :
nodeList[first].append(second)
else :
nodeList[first] = [second]
return nodeList
def _2606() :
computerN = int(input())
computerPairNum = int(input())
nodeList = {}
# 입력을 받고, 노드를 이어줍니다.
for _ in range(computerPairNum) :
first, second = map(int, input().split(' '))
nodeList = addNode(first,second,nodeList)
nodeList = addNode(second,first,nodeList)
# DFS 수행
visited = []
stack = [1] # start node
while stack :
node = stack.pop()
if node not in visited and node in nodeList : # node가 nodeList에 key로 존재
visited.append(node)
stack += list(set(nodeList[node]) - set(visited))
# print(visited)
return len(visited)-1
print(_2606())
파이썬은 최대 재귀 깊이가 정해져 있습니다. 물론 라이브러리를 활용하여 최대 재귀 깊이를 수정해줄 수도 있지만, 불필요한 작업을 피하기 위해 통상 DFS/BFS를 재귀없이 풀이하는 경우가 많다고 합니다.
C++을 사용하던 저로서는 무언가 불필요하게 복잡도를 늘리는 작업을 하는 것만 같아 마음이 불편하네요… 백준은 복잡도 기준이 엄격한 편이므로, 일단 재귀없이 풀어보다가 복잡도에 걸리게 되면 그 때에 다시 재귀로 시도해보겠습니다.