[백준1325&파이썬] DFS+DP는 사이클이 없을때 사용 가능하다.

# 문제

백준 1325 효율적인 해킹 DFS 풀이

1325번: 효율적인 해킹

 

# 코드

import sys
from collections import defaultdict
from collections import deque


N,M = map(int, sys.stdin.readline().split())
# 1 ~ N 까지 컴퓨터의 번호가 주어짐
# M개의 줄에 신뢰하는 관계 형성

ddict = defaultdict(list)

for i in range(M) :
  a,b = map(int, sys.stdin.readline().split())
  ddict[b].append(a) # A가 B를 신뢰한다. B -> A / B를 해킹하면 A를 알 수 있다.

# ###---시간초과 -> PyPy 제출 풀이 ---###
counter = [-1] * (N+1)
mmax = 0
for index in range(1,N+1) :
  visited = [False] * (N+1)
  stk = deque()
  stk.append(index)
  visited[index] = True

  cnt = 0
  while len(stk) != 0 :
    cur = stk.pop() # 뽑기

    for next in ddict[cur] :
      if visited[next] == False :
        cnt += 1
        visited[next] = True
        stk.append(next)

  counter[index] = cnt
  mmax = max(cnt,mmax)

for index,item in enumerate(counter):
  if item == mmax :
    print(index,end=" ")
    
    
### ----- ###
# DP와 DFS를 활용해서 풀어보자
# memo = [-1] * (N+1)
# mmax = 0
# def dfs(cur) :
#   global mmax
#
#   if len(ddict[cur]) == 0 : # 맨마지막이면
#     return 1
#
#   if memo[cur] != -1 :
#     return memo[cur]
#
#   cnt = 0
#   for next in ddict[cur] :
#     cnt += dfs(next)
#
#   memo[cur] = cnt + 1
#   mmax = max(cnt+1, mmax)
#   return memo[cur]
#
# for i in range(1,N+1) :
#   dfs(i)
#   # memo[i] -= 1
#   # print(f"{i} : {memo}")
#
# for index,item in enumerate(memo) :
#   if item == mmax :
#     print(index,end=" ")
#

 

# 풀이

• BFS가 풀기 더 편한거 같다. DFS를 연습하기 위해서 DFS로 풀었다. 
• 기존 시도에서 DFS가 시간초과(파이썬 제출) 나오길래 DFS + DP를 이용해서 풀었는데 리컬젼에러가 등장했다. 해당 문제가 노드간 단방향 연결이고, 사이클이 존재해버리는 경우가 생기기 때문에 순환참조가 일어나는거 같다는 추측을 해봤다. 왜냐하면 난 visited를 처리하지 않았기 때문이다.
• visited를 처리한다고 하면 순환 참조 구간에서 memo가 잘못 될거라는 생각이 들었다.
• 질문게시판 좀 돌아보니 DFS를 pypy로 제출하면 된다해서 완료했다.

## DFS에서도 방문처리를 하자

• DFS에서도 방문처리를 해야한다. 난 특히 단방향일때는 안해도 된다고 생각했는데, 사이클이 형성될 수 있었다.