DFS 알고리즘 #프로그래머스 #타겟넘버 | 파이썬 풀이

📚  문제

원본: https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3 

코딩테스트 연습 - 타겟 넘버

💡 접근법

⚙️ 활용 알고리즘: DFS

 

저의 접근법은 다음과 같습니다.

DFS 알고리즘을 중심으로 0부터 시작하여 부모 노드에 number를 더하거나 빼는 작업을 동시에 수행하여 자식 노드를 생성하고,

해당 자식 노드를 다시 부모 노드로 치환해 위 작업을 반복 수행하며  target과 같아지는 경우의 수를 모두 카운팅해 주는 것입니다.

그림 1. DFS 알고리즘 활용한 구현

위의 접근법으로 본 문제에서 주어지는 입력 예시1이 어떻게 동작하는지 그림 1 을 중심으로 살펴보겠습니다.

먼저 ①번 그래프를 보시면, 0이 부모 노드(super node)이고, 이 부모 노드에 1을 더하거나 빼 자식 노드를 생성합니다.

이제 ②번 그래프를 보시면, 앞서 생성한 자식 노드들이 이제 부모 노드가 되고,

각 노드별로 다시 1을 더하거나 빼는 작업을 수행합니다.

위의 과정을 주어진 numbers 개수만큼 수행했을 때 최종적으로 얻어지는 노드 중에서

target과 일치하는 노드의 개수를 카운트 해주면 정답이 됩니다 :)

💻  My solution

def solution(numbers, target):
    super_node = [0]
    for number in numbers:
        sub_node = []
        for sup in super_node: 
            sub_node.append(sup + number)
            sub_node.append(sup - number)
        super_node = sub_node
        print(super_node)
    return super_node.count(target)

👀 참고할 만한 포스팅

이론 자료
1.  [알고리즘] 너비 우선 탐색(BFS) 알고리즘에 대해 알아보자!(+Python 구현)
2.  [알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)
3.  [파이썬] map 함수에 대해 알아보자(Feat. lambda 표현식)
4.  [자료구조] 큐(Queue)에 대해 알아보자(+ Python)

관련 문제
1.  BFS 알고리즘 | 백준#11123 #실버 | "양 한 마리, 양 두 마리" | 파이썬 풀이
2.  BFS 알고리즘 | 백준#17086 #실버 | "아기상어2" | 파이썬 풀이
3.  DFS 알고리즘 #프로그래머스 #타겟넘버 | 파이썬 풀이
4.  BFS알고리즘 #프로그래머스 #가장 먼 노드 | 파이썬 풀이

---

문제 풀이 피드백이나 질문 환영합니다. 아래에 댓글 남겨주세요!👍

그럼 오늘도 건강하고 즐거운 하루 보내시길 바랍니다 :)

고맙습니다.