그래프탐색 DFS | 프로그래머스 고득점kit 타겟 넘버 | Python

created_at : 13 May 2024 - 2 mins read time
Tags: 그래프탐색

프로그래머스 고득점kit 타겟 넘버 | Python
- 🔎 문제 설명
- 💻 내 코드
  - 1️⃣ DFS를 이용한 코드
  - 2️⃣ 재귀를 이용한 코드

프로그래머스 고득점kit 타겟 넘버 | Python
- 🔎 문제 설명
- 💻 내 코드
  - 1️⃣ DFS를 이용한 코드
  - 2️⃣ 재귀를 이용한 코드

프로그래머스 고득점kit 타겟 넘버 | Python

🔎 문제 설명

💚 Level 2

- 난이도 ★☆☆☆
- 그래프탐색 DFS

그래프탐색 DFS를 이용하면 그리 어렵지 않은 문제다. 사실 그냥 다 더하고 빼서 target 점수가 되는 값만 세어도 된다. 그러나 재귀로 엄청 깔끔하게 코드로 작성할 수 있어서 가져와 보았다.

💻 내 코드

1️⃣ DFS를 이용한 코드

answer = 0

def dfs(idx, now, target, numbers):
    global answer
    num_len = len(numbers)
    if idx == num_len and now == target:
        answer += 1
    if idx < num_len:
        dfs(idx+1, target, now - numbers[idx], numbers)
        dfs(idx+1, target, now + numbers[idx], numbers)
    return

def solution(numbers, target):
    dfs(0, 0, target, numbers)
    return answer

2️⃣ 재귀를 이용한 코드

def solution(numbers, target):
     # numbers 끝까지 순회하고 target 값 달성했을 때
     if not numbers and target == 0:
          return 1
     # numbers 끝까지 순회했지만 target 값 달성 못했을 때
     elif not numbers:
          return 0
     else:
          return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).