[Python] 프로그래머스 - 타겟 넘버

1. 문제정보

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

2. 풀이

우선 주어진 문자열 정보를 가지고 DFS를 사용하기 위해 다음과 같은 이상한 그래프(?)로 만들었다. 이상하다고 표현한 이유는 노드간의 연결도 아니고, 좌표간의 연결도 아니기 때문에 이렇게 표현했다. 지금 생각해보니 없어도 되는 로직인데.. 어쨌든 DFS에 0을 전달하며 탐색이 시작할 수 있도록 구현했다. 

[
	[1, -1], # 0번째에서 선택할 수 있는 수
	[1, -1], # 1번째에서 선택할 수 있는 수
	[1, -1], # 2번째에서 선택할 수 있는 수
	[1, -1], # 3번째에서 선택할 수 있는 수
	[1, -1]  # 4번째에서 선택할 수 있는 수
]

 

3. 소스코드

풀이 1. 이상한 그래프(?) 사용

def dfs(graph, n, cnt):
    result = []
    if n == len(graph):
        return [cnt]
    else:
        link = graph[n]
        for v in link:
            sum = dfs(graph, n+1, cnt+v)
            result += sum
    return result

def solution(numbers, target):
    graph = []
    for i in range(len(numbers)):
        graph.append([numbers[i], numbers[i]*-1])

    answer = 0
    result = dfs(graph, 0, 0)
    for r in result:
        if target == r:
            answer += 1
    return answer

 

풀이2. 소스코드 개선

answer = 0
def dfs(numbers, idx, target, sum):
    if len(numbers) == idx and target == sum:
        global answer
        answer += 1
    elif len(numbers) == idx:
        return
    else:
        dfs(numbers, idx+1, target, sum + numbers[idx])
        dfs(numbers, idx+1, target, sum + numbers[idx]*-1)

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

 

4. 배운점

그동안 DFS/BFS를 풀면서 주어진 노드 또는 배열을 기준으로만 구현을 하다보니 주어진 문제를 DFS로 구현하는데 어려움이 들었다. 그래서 습관적으로 그래프를 만들려고했지만 노드의 연결도 아닌 이상한 그래프(?)가 만들어진 것 같다. 습관적인 풀이가 아닌 문제를 이해하고 해결하기 위한 로직을 찾아내는 훈련이 필요할 것 같다.