[프로그래머스] DFS/BFS - 타겟 넘버
🎯 programmers : 깊이/너비 우선 탐색 - 타겟 넘버
🤔 나의 풀이
📌 문제
- 프로그래머스 코딩테스트 연습 > 깊이/너비 우선 탐색 > Level 2 타겟 넘버
📌 날짜
2021.03.09
📌 시도 횟수
5 try
💡 Code
answer = 0
def solution(numbers, target):
max_idx = len(numbers) - 1
def dfs(idx, num, cur_sum): # -1, 0, 0 부터 시작해야됨
global answer
cur_sum += num
if idx == max_idx:
if cur_sum == target:
answer += 1
return
idx += 1
num = numbers[idx]
dfs(idx, num, cur_sum)
dfs(idx, -num, cur_sum)
dfs(-1, 0, 0)
return answer
💡 문제 해결 방법
- dfs 재귀를 실행할 때마다 idx(인덱스) 값을 1씩 늘렸다. (마치 for문처럼 동작한다)
- 만약 현재 idx가 len(numbers)-1 가 되었다면 현재까지의 path를 모두 더한
cur_sum이 target과 일치하는지 검사한다.
- 참고로 dfs를 시작할 때 주는 루트 값의 idx를 -1로 주어
다음 재귀때부터 (idx + 1 = 0) 0이 되어 정상적으로 동작하도록 설정해주었다.
💡 새롭게 알게 된 점
-
❌ (한번에 맞추지 못한 경우) 오답의 원인
-
위의 코드를 좀 더 깔끔하게😄
answer = 0 def solution(numbers, target): global answer answer = 0 def dfs(cur_sum, idx): global answer if idx == len(numbers): if cur_sum == target: answer += 1 return dfs(cur_sum - numbers[idx], idx + 1) dfs(cur_sum + numbers[idx], idx + 1) dfs(0, 0) return answer
Author And Source
이 문제에 관하여([프로그래머스] DFS/BFS - 타겟 넘버), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@eunseokim/프로그래머스-DFSBFS-타겟-넘버저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)