[프로그래머스] 깊이/너비 우선 탐색 - ( 전부 조사하는 방법 )

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

풀이

numbers = [1,1,1,1,1] 인 경우 4층 까지 list 배열

numbers = [ 1,1,1,1,1 ] 인 경우의 예를 들어보자. 그림에서는 4층까지 나타냈지만, 한층 더 내려가야한다.

한 층 내려갈 때마다, 이전 숫자에서 numbers 배열의 다음 숫자를 더하고 빼는 경우의 수를 취해준다.

새로운 배열을 만드는 것이 아닌, list의 슬라이싱을 잘 이용하여 층을 구분짓는다.

 

append는 2^x 개씩 늘어나고, 시작 idx 는 2x+1 씩 갱신하면 된다. 

최종 층에 도달했을 때, target 값을 count 하자.

def solution(numbers, target):
    idx = 0
    arr = [0]
    
    for i in numbers:
        for j in range(idx, len(arr)):
            arr.append(arr[j] + i)
            arr.append(arr[j] - i)
        idx = 2*idx + 1
    return arr[2**(len(numbers)):].count(target)

 

DFS와 BFS를 연습하기 위해 다른 풀이를 더 참고했다.

>> DFS

def DFS(n, order, numbers, target):
    if order == len(numbers)-1:
        if n == target:
            return 1
        
        return 0
    
    case1 = DFS(n+numbers[order+1], order+1, numbers, target)
    case2 = DFS(n-numbers[order+1], order+1, numbers, target)
    
    return case1 + case2

def solution(numbers, target):
    num =0
    num = DFS(numbers[0], 0, numbers, target) + DFS(-numbers[0], 0, numbers, target)
    return num

좌우로 뻗은 노드를 0/1 으로 return 하여  총 합을 계속 더해가는 방식이다.

 

>> BFS

from collections import deque

def solution(numbers, target):
    answer = 0
    
    q = deque()
    q.append((numbers[0], 0))
    q.append((-numbers[0], 0))
    
    while q:
        n, order = q.popleft()
        
        if order == len(numbers)-1:
            if n == target:
                answer += 1
            continue
        
        q.append((n+numbers[order+1], order+1))
        q.append((n-numbers[order+1], order+1))
    
    return answer

먼저 입력된 정보를 꺼내면서 다음 노드로 연결한다.

 

출처

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스