프로그래머스 BFS/DFS 문제입니다. 알고리즘 숙달을 위한 문제 반복풀이입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이1]

⌛ 소요 시간 53분

def solution(numbers, target): 
    
    answer = 0

    result = [0]

    while numbers:
        result2 = []
        num = numbers.pop()

        for res in result:
            result2.append(res+num)
            result2.append(res-num)

        # print(result2)
        result = result2

    for res2 in result2:
        if res2 == target:
            answer += 1

    return answer

입력값으로 주어진 요소에 대해 덧셈 혹은 뺄셈의 모든 경우의 수를 구하기위해
다음값을 이전 연산 결과 모든 요소들에 + 하거나 - 하는 알고리즘으로 해결하였습니다. 연산한 리스트의 요소 갯수가 이전 갯수 대비 x2배씩 늘어나는 구조입니다.

[나의 풀이2]

⌛ 과거 풀이

def solution(numbers, target) : 
    
    answer = 0
    
    # 값,인덱스
    stack = list([[numbers[0],0],[numbers[0]*(-1),0]])
    print(stack)

    while stack:
        
        v,n = stack.pop()

        if n < len(numbers)-1:
            n += 1
            stack.append([v+numbers[n],n])
            stack.append([v-numbers[n],n])
        
        else:
            if v == target:
                answer += 1

        print(stack)
    
    return answer

과거 풀이로써 + 혹은 - 연산한 결과를 append하고 이를 한가지 케이스의 모든 연산이 끝날 때까지 반복하는 것을 우선으로 하는 DFS 구현 풀이였습니다. 현재 연산한 값(v), 현재까지 연산한 횟수(n)를 표현하여 해결한 풀이입니다.

[나의 풀이3]

⌛ 과거 풀이

def solution(numbers, target) : 
    
    answer = 0
    
    from collections import deque
    
    # 값,인덱스
    queue = deque([[numbers[0],0],[numbers[0]*(-1),0]])
        
    while queue:
        
        v,n = queue.popleft()

        if n < len(numbers)-1:
            n += 1
            queue.append([v+numbers[n],n])
            queue.append([v-numbers[n],n])
        
        else:
            break
        
    for x in queue:
        if x[0] == target:
            answer += 1
    
    return answer

비슷한 방식이지만 위 풀이와 다르게 BFS 구조로 구현한 풀이입니다. 이전에 연산한 요소들에 덧셈 혹은 뺼셈 연산을 하되 모든 케이스에 대해 연산한 횟수가 같게끔 너비 우선 탐색으로 구현한 풀이입니다.

감사합니다.