[Python] 프로그래머스 level2 타겟넘버 (BFS/DFS)

mog·2020년 11월 26일
30

타겟넘버 문제를 bfs와 dfs를 이용해서 풀어봤다. 아래 나오는 코드들은 다 모든 테스트케이스를 통과한 코드이다!

👀 타겟넘버가 왜 BFS/DFS 문제인가?

👀 deque를 이용한 BFS 풀이

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer
# stack을 이용한 dfs여도 마찬가지! 
def solution(numbers, target):
    answer = 0
    queue = [[numbers[0],0], [-1*numbers[0],0]]
    n = len(numbers)
    while queue:
        temp, idx = queue.pop()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

👀 재귀함수를 이용한 DFS 풀이

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0,0)
    return answer

💡 위 코드에서 nonlocal을 처음 보신다면 관련포스팅을 참고!

8개의 댓글

comment-user-thumbnail
2021년 3월 19일

좋은 설명 감사합니다..!

답글 달기
comment-user-thumbnail
2021년 8월 24일

재귀함수의 대한 이해도가 높아졌습니다. !!!!! 꿋뜨 good

답글 달기
comment-user-thumbnail
2021년 11월 6일

덕분에 이해했어요~ 감사합니다!

답글 달기
comment-user-thumbnail
2022년 4월 19일

저... 밑에서 numbers 배열 +또는 - 계산하고있는데 왜 queue에 [[numbers[0],0],[-1numbers[0],0]해주는건가요?? queue = [[numbers[0],0],[-1numbers[0],0] 이 부분 부가 설명 부탁드립니다! queue 초기화 인가요??

1개의 답글
comment-user-thumbnail
2022년 4월 20일

내공이 느껴지는 깔끔한 코드와 설명이네요. 잘 읽었습니다!

답글 달기
comment-user-thumbnail
2022년 9월 8일

감사합니다!

답글 달기
comment-user-thumbnail
2022년 10월 5일

감사합니다.

답글 달기