2019.03.01) 백준 dfs 특집 1편 - 1182, 6603(PyPy3)

dfs는 간단하게 재귀로서 구현할수 있다.

하지만 최적화 하려면 반복문으로 구현해야하는게 사실이긴 하지만

여기선 다 2초줘서 적당히 풀었다.

1182번

a, b = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
 
c = 0
 
 
# 깊이 위주 서치
def dfs(now, index):
    global c
    # 배열 길이보다 더 텀색할순 없으니
    if index == a:
        return
    # 만약 합이 제시된것과 같으면
    if now + l[index] == b:
        # 카운터 추가
        c += 1
 
    # 현재값에서 서치된곳의 값을 합치고 넘기고
    dfs(now + l[index], index + 1)
    # 현재값에서 서치된곳의 값을 안 합치고 넘기고
    dfs(now, index + 1)
 
 
dfs(0, 0)
 
print(c)
 

6603번

# 깊이 위주 서치
def dfs(lis, index):
    # 남은 배열의 길이가 6번을 채울정도로 길지 않으면
    if 6 - len(lis) > len(a) - index:
        return
    # 만약 길이가 6이면
    if len(lis) == 6:
        print(' '.join(lis))
        return
    # 배열 복사
    tmp = lis[:]
    tmp.append(a[index])
    # 현재값 추가해서 넘기고
    dfs(tmp, index + 1)
    # 현재값 안추가해서 넘기고
    dfs(lis, index + 1)
 
 
while True:
    # .join을 쓰기 위해 문자열로서 처리
    a = input().split(' ')
    if a[0] == '0':
        break
    dfs([], 1)
    print()