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

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

프로그래머스

 

 

문제 해결 포인트

- Queue를 이용하여 BFS로 탐색

- 모든 numbers의 요소에 대해서 +와 -를 조합하다가 모든 수를 사용했다면 그 때 target과 값이 같은지 비교

- queue에 계산된 값과 사용된 숫자 개수를 같이 삽입함으로써 무한루프에 빠지지 않게 함

- 즉 pop한 결과가 아직 모든 숫자를 사용하지 않았다면 다음 숫자를 더하고 뺀 값을 다시 queque에 삽입

 

작성 코드

from collections import deque
def solution(numbers, target):
    que = deque()  # deque 선언
    result = 0
    que.append((numbers[0], 1))  # '결과 값'과 '사용된 숫자 개수' 삽입
    que.append((-numbers[0], 1))
    while que:  # queue에 값이 있을 때까지 반복
        q = que.popleft()  # 맨 앞 데이터 빼기
        if q[1] == len(numbers):  # 주어진 모든 수를 사용하여 계산 했을 때
            if q[0] == target:  # 결과 값이 찾던 값과 같다면
                result += 1
        else:
        	# '현재까지 결과 +- 다음 수', '사용된 수+1'
            que.append((q[0]+numbers[q[1]], q[1]+1))  
            que.append((q[0]-numbers[q[1]], q[1]+1))  
    return result

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚