프로그래머스 dfs/bfs 타겟넘버 python

프로그래머스 dfs/bfs 타겟넘버 python (난이도 level2)

 

- 문제

 

 

- 문제 해설

주어진 numbers로 모든 경우의 수를 따져야 하는 문제이므로 dfs, bfs로 접근

 

- 실수했던 point

q 초깃값에 -numbers[0] 를 추가할 생각을 못했음 (이번에는 테케를 보고 바꿨지만, 예제에 없으면 틀렸을뻔)

q.popleft() 대신 q.pop()을 대신 사용함

코드를 정리하지 않고 작성하다가, 생각이 막혀서 변수 다시 정의 

 

- solution (bfs 로 접근)

from collections import deque

cases = [-1, +1]
q = deque()    

def solution(numbers, target):
    answer = 0
    cnt = 0
    q.append([numbers[0], cnt])
    q.append([-numbers[0],cnt])
    
    while(len(q)>=1):
        cur_number, cur_cnt = q.popleft()
        new_cnt = cur_cnt + 1

        if new_cnt < len(numbers):
            for case in cases:
                new_num = case*numbers[new_cnt]
                new_sum = cur_number + new_num
                    
                if new_sum == target and new_cnt == len(numbers)-1:
                    #print('answer', new_sum)
                    answer += 1
                else:
                    q.append([new_sum, new_cnt])
            #print('q',q)
        #print('\n')

    return answer