[Programmers] 타겟 넘버(Python) / DFS

프로그래머스 고득점 KIT > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > Level 2 타겟 넘버 문제이다.

programmers.co.kr/learn/courses/30/lessons/43165?language=python3

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

발상으로는 매우 쉬운 수준의 문제인데, 함수 내 전역변수 사용법 때문에 생각보다 헤맸다.

 

늘 백준, SWEA 문제로만 연습하다보니 완전탐색할 때 전체 갯수, 최대 갯수, 최솟값 등을 갱신하는 문제에서 별 생각없이 함수 밖에 변수를 정의하고 함수 내에 전역변수(ex. global answer)를 사용했었다.

사실 이것도 그리 다를 건 없었다.

solution 함수에서 호출한 dfs 함수를 answer을 인자로 넘겨서 갱신하려고 했는데 재귀가 풀리면서 이 또한 계속 0으로 풀렸다.

이는 간단하게 두 함수 모두 안에 전역변수 선언을 하면 됐던 것.

 

재귀로 순열을 구현하였고, -1, 1 중 하나를 선택할 때마다 계산을 해서 인자로 넘겼다.

인자로 최소한의 필요한 정보들만 넣도록 했다.

여기서 시간 단축을 많이 시킬 수 있었다.

타겟 넘버를 만나면 그 때 전역변수 answer += 1 해주니 답이 잘 나왔다.

 

파이썬 코드는 다음과 같이 간단하게 구현했다.

---

def dfs(depth, numbers, target, N, temp):
    global answer
    if depth == N:
        if temp == target:
            answer += 1
        return
    for i in (-1, 1):
        dfs(depth+1, numbers, target, N, temp + i*numbers[depth])

def solution(numbers, target):
    global answer
    answer = 0
    N = len(numbers)
    dfs(0, numbers, target, N, 0)
    return answer

---

* 고찰 : 마찬가지로 전역변수는 함수 내 global로 선언해주면 사용할 수 있다. 기초적인 건데 이제라도 알아서 다행^_ㅎ