타겟넘버 문제를 bfs와 dfs를 이용해서 풀어봤다. 아래 나오는 코드들은 다 모든 테스트케이스를 통과한 코드이다!
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
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
을 처음 보신다면 관련포스팅을 참고!
좋은 설명 감사합니다..!