[프로그래머스]타겟 넘버

프로그래머스

타겟 넘버

링크 : 문제 바로가기

def solution(numbers, target):
    answer = 0

    stack=[[0,-1]]
   
    while len(stack)!=0:
        # print("스택은",stack)
        checking=stack.pop()
        # print(checking)
        sums=checking[0]
        i=checking[1]

        if i >=len(numbers)-1: # 모든 수를 다 더한 것임. target과 비교한뒤 answer에 반영
            if sums==target:
                answer+=1
            continue

        stack.append([sums+numbers[i+1],i+1])
        stack.append([sums-numbers[i+1],i+1])

    return answer

DFS를 이용해 풀었다. 예를 들어 numbers가 [1,2,3]이라면 처음에 시작은 0에서 시작하고 다음과 같은 그래프를 생각한다.

즉, numbers가 총 n개의 요소를 가지고 있다면 2^(n)개 만큼의 경우의 수를 가지는 그래프를 만들고 이 그래프를 DFS로 탐색한 것이다. 이때 일반적인 DFS탐색과 달리 그저 탐색만 하는 것이 아니라 막다른 곳에 다다랐을 때 최종값을 구해 이것이 target과 같은지 비교해야 했고, 막다른 곳에서 뒤로돌아가 다른 길을 찾을 때는 그 지점에서의 총합을 다시 구해야했다(예를 들어 ‘0 -> -1 -> -2 -> -3’에서 -3이 아닌 +3을 선택한 경우로 되돌아갈 때 0+(-1)+(-2)+(-3)값에서 다시 +(-3)을 해준 값에서 +3을 선택해야 한다). 이런 점때문에 정점들을 선택한 numbers요소값이 아닌, 여태까지 총합 + 선택한 numbers요소값으로 표현했다. 또한 해당 정점에서 더해야 할 numbers요소가 몇번째인지를 확인하기 위해 numbers인덱스 확인용 정보도 같이 넣었다.

알고리즘 : 깊이/너비 우선 탐색(DFS/BFS)