DFS 함수 탈출

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

4. 합이 같은 부분집합(DFS)

작성

483

안녕하세요 선생님 강의 열심히 듣고 있는 학생입니다 !

강의 듣고 나서 복습하다가 아래와 같이 풀었는데요.

이 경우에 sum과 total-sum 조건을 비교하는 부분을 한 번만 통과하면 바로 DFS함수를 끝내는 방법이 있을까요?

return을 해도 계속 통과를 해서 질문 드립니다 ! 감사합니다.

def DFS(L, sum):
  global answer
  if L==len(nums):
    if sum == total-sum:
      answer = "YES"
      
  else:
    DFS(L+1, sum+nums[L])
    DFS(L+1, sum)
    


if __name__ == "__main__":
  n = int(input())
  nums = list(map(int, input().split()))
  answer = "NO"
  total = sum(nums)
  DFS(0, 0)
  print(answer)

코테 준비 같이 해요! python

답변 1

김태원

지식공유자

안녕하세요^^

신호변수를 하나 두고 답을 구하면 그 다음 호출들은 호줄되자마자 바로 종료하면 됩니다.

def DFS(L, sum):
  global answer, flag
  if flag:
     return
  if L==len(nums):
    if sum == total-sum:
      answer = "YES"
      flag = True
      
  else:
    DFS(L+1, sum+nums[L])
    DFS(L+1, sum)
    


if __name__ == "__main__":
  n = int(input())
  flag = False
  nums = list(map(int, input().split()))
  answer = "NO"
  total = sum(nums)
  DFS(0, 0)
  print(answer)

kimcola

질문자

와.. 감사합니다 !!

인프런 커뮤니티 질문&답변

DFS 함수 탈출