DFS 함수 탈출

Introduction to Python Algorithm Problem Solving (Coding Test Preparation)

4. Subsets with the same sum (DFS)

Written on

480

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

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

이 경우에 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

Answer 1

codingcamp

Instructor

안녕하세요^^

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

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

Questioner

와.. 감사합니다 !!

Inflearn Community Q&A

DFS 함수 탈출