[프로그래머스/Python] 알고리즘고득점Kit-DFS/BFS-타겟넘버

📌  문제링크

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

프로그래머스

 

📌  문제설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

# 제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

📌 풀이과정 

✅  1번째 시도: FAIL 

answer = 0
def solution(numbers, target):
    global answer
    visited = [0] * len(numbers)
    dfs(0, numbers, visited, target)
    return answer

def dfs(result, numbers, visited, target):
    global answer
    print(result)
    if result == target:
        answer += 1
    for i, n in enumerate(numbers):
        if not visited[i]:
            print(f"now i = {i} n = {n}")
            visited[i] = 1 
            dfs(result+n, numbers, visited, target)
            dfs(result-n, numbers, visited, target)

 

왜일까 고민을 해봤다. 테스팅 코드를 삽입해서 실행해보니까 아래 사진처럼 나왔다.

한번 방문한 곳은 방문하면 안되는 거 아닌가.. => 이건 그래프 노드 이런거 할 때지 지금은 다르다.

따라서 visited가 필요하지 않다. 

 

✅ 2번째 시도: pass

• 인수로 index값을 넘겨 모든 원소를 방문할 수 있게 했다. 
• 시행착오
  • dfs()의 if문 i==len(numbers)-1로 설정했더니 계속 answer 값이 0이 나왔다. 
  • 이유가 뭘까 생각했더니, 마지막까지 계산할 수 없게 만들어놨고, 정작 마지막까지 계산해서 돌아오니까 result == target를 검사할 수 없게 만들어놨던 것이다. (like 아래 일부 코드처럼..) 

if i == len(numbers)-1 and result == target: 
        answer += 1
        return

 

 

그래서 아래의 풀이코드로 후다닥 변경했더니 pass되었다. 휴.. 

 

📌  풀이코드

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

def dfs(i, result, numbers, target):
    global answer
    if i == len(numbers) and result == target: 
        answer += 1
        return 
    elif i == len(numbers):
        return 
    dfs(i+1, result+numbers[i], numbers, target)
    dfs(i+1, result-numbers[i], numbers, target)