• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

문제 6-4 <합이 같은 부분집합>

20.05.28 20:52 작성 조회수 71

0

안녕하세요 선생님. 강의 잘 듣고있습니다.

문제 6-4번 풀던 중에 궁금한점이 생겼는데요. 

dfs 함수의 if문에서 조건을 충족하면 True를 리턴하고, 맨 마지막에 있는 if문을 통해 yes를 프린트 하려고 했는데,
None이 출력되는 이유가 궁금합니다!

```

# 합이 같은 부분집합

import sys
sys.stdin = open('input4.txt', 'r')

n = int(input())
fo = list(map(int, input().split()))
result = [0]*n

def dfs(k):
summ = 0
if k == n :
for i in range(n):
if result[i] == 1 :
summ += fo[i]
if summ*2 == sum(fo) :
return True
else :
result[k] = 1
dfs(k+1)
result[k] = 0
dfs(k+1)

print(dfs(0))
if dfs(0):
print("YES")
else :
print("NO")
```

답변 1

답변을 작성해보세요.

0

감사합니다^^

def DFS(n):
    if n==5:
        return True
    else:
        DFS(n+1)
    
if __name__=="__main__":
    print(DFS(0))

위 코드는 DFS(5)만 True를 리턴받고 그 값이 DFS(0)까지 전달이 되지 않아 DFS(0)은 None값을 갖는 코드입니다.

def DFS(n):
    if n==5:
        return True
    else:
        return DFS(n+1)
    
if __name__=="__main__":
    print(DFS(0))

위 코드는 DFS(5)가 True를 리턴받고, DFS(4)는 DFS(5)를 린턴받고 하면서 초종적으로 DFS(0)은 DFS(1)를 리턴받아 True를 리턴받게 됩니다. 

이 문제처럼 함수 호출이 여러갈래로 이루어질 때는 함수가 값을 리턴받는게 아리라 변수를 사용해서 해결합니다. (exit() 없이 해결할 때)

def DFS(L):
    global res
    if res: return
    if L == n:
        Sum=0
        for i in range(n):
            if result[i]==1:
                Sum+=a[i]
        if Sum*2==sum(a):
            res=True            
    else:
        result[L]=1
        DFS(L+1)
        result[L]=0
        DFS(L+1)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    result=[0]*n
    res=False
    DFS(0)
    if res:
        print("YES")
    else:
        print("NO")