[백준] 2606 바이러스

07 Apr 2021

문제

파이썬으로 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++을 사용하던 저로서는 무언가 불필요하게 복잡도를 늘리는 작업을 하는 것만 같아 마음이 불편하네요… 백준은 복잡도 기준이 엄격한 편이므로, 일단 재귀없이 풀어보다가 복잡도에 걸리게 되면 그 때에 다시 재귀로 시도해보겠습니다.