[프로그래머스] 타겟넘버 - python 파이썬

문제

 

dfs/bfs 문제이기는 한데 평소에 풀던 방식과는 조금 다르게 풀어야해서 애를 먹었다....

 

일단 이 문제의 관건은 numbers 배열을 돌면서 상위노드의 값에 아래의 노드값을 계산하는 방식으로 내려가 주어야 한다.

 

전체코드

def solution(numbers, target):
    answer = 0
    
    leaves = [0]
    
    for num in numbers:
        tmp =[]
        #leaves는 이전의 노드
        for leaf in leaves:
            tmp.append(leaf-num)
            tmp.append(leaf+num)
            
        leaves = tmp
            
    answer = leaves.count(target)        
    
    return answer

 

 

 

코드를 설명하자면 일단 처음에는 leaves를 0으로 두어 첫번째 값의 음수야 양수버전이 들어갈 수 있도록 해주었고

leaves는 현재노드 이전의 노드로 현재노드의 음수와 양수버전을 더해주면 된다.

 

그 후 현재노드가 더해진 tmp를 leaves에 넣어 다음 노드를 구할 때 이 leaves를 활용할 수 있도록 해주었다.

 

이거는 bfs를 활용한 풀이라고 보면된다. 다만 queue를 활용하지 않고 노드의 깊이별로 저장해서 다음단계의 노드와 계산해 업데이트해주는 형식이다.