[프로그래머스 DFS/BFS]타겟 넘버 - Python3

문제

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

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

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

• -1+1+1+1+1 = 3
• +1-1+1+1+1 = 3
• +1+1-1+1+1 = 3
• +1+1+1-1+1 = 3
• +1+1+1+1-1 = 3

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

제한사항

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

 

입출력

numbers	target	return
[1, 1, 1, 1, 1]	3	5

알고리즘

def iterative_solution(numbers, target):
    # result_list는 0부터 시작한다. 그리고, [0, 0-a, 0+a, 0-a-b, 0-a+b, 0+a-b, 0+a+b, ... ] 이런 식으로 간다.
    result_list = [0]

    # i는 numbers의 각 원소들
    for i in range(len(numbers)):
        temp_list = []

        # result_list는 0부터 numbers의 각 원소들을 빼고 더한 값들이 있다.
        for j in range(len(result_list)):
            temp_list.append(result_list[j] - numbers[i])
            temp_list.append(result_list[j] + numbers[i])
        result_list = temp_list
        print(result_list)

    return result_list.count(target)

<반복적 DFS로 푸는 코드>

answer = 0


def dfs(numbers, target, length, i):
    global answer
    if i == len(numbers):
        if (sum(numbers)) == target:
            answer += 1
            return
    else:
        dfs(numbers, target, length, i+1)
        numbers[i] *= -1
        dfs(numbers, target, length, i+1)


def recursive_solution(numbers, target):
    global answer
    length = len(numbers)
    dfs(numbers, target, length, 0)

    return answer

<재귀적 DFS로 푸는 코드>

설명

이 문제는 DFS로 풀었다. 왜냐하면, 어떤 데이터가 그래프(노드와 엣지로 이루어진 자료구조 - 섹시한 개발자)의 형태로 이루어져있고, 그래프의 끝에 있는 노드(leaf 노드)까지 가서, 그 값까지 더하거나 뺸 값을 얻어야 하기 때문이다. 이런 경우는 BFS보다는 DFS로 푸는 것이 나을 것이라 생각했다.

이 문제를 풀기위해서는, 다음과 같은 트리 구조의 형태를 생각해야 한다. 그림의 편의를 위해, [a, b]  이런 형태의 입력이 들어온다고 치자. 

이런 식으로 데이터를 만든다 생각하고, 각 끝에 있는 노드까지의 합을 더하면, 그것이 하나의 결과값이 된다. 이 결과값을 모두 모아서, target과 같은지 살펴보고, target과 같은 경우의수 만큼을 리턴한다. 

즉, 결과값들은 [ 0+A+B, 0+A-B, 0-A+B, 0-A-B] 이렇게 되고, 이 중에 target과 같이 같은 원소의 갯수가 정답이 되는 것이다. 

첫 번째 코드는 DFS를 반복적으로 구현한 코드이다.

1. 초기의 배열인 result_list를 [0]으로 초기화한다. 
2. i가 numbers의 원소길이만큼 반복하면서, temp 배열을 생성한다. 
   1. j가 result_list의 원소만큼 반복한다.
      1. temp배열에 result_list[j] - numbers[i], result_list[j] - numbers[i] 두 값을 append한다. 이것은, 0 + A, 0 - B의 값을 temp_list에 붙여둔다는 것이다. 
   2. result_list에서의 반복이 끝나면, 생성된 temp_list를 result_list에 덮어쓴다. 이로써, 0층(가장 위)에 있는 노드들을 1층(그 아래층)에 있는 노드들을 더하고 뺀 결과를 누적시킨다.
3. 이렇게 반복을 2중 for문이 반복을 마치게 되면, result_list의 각 원소들은 numbers에 있는 모든 원소들을 더하거나 빼서 얻을 수 있는 모든 결과값을 가지게 된다. 
4. result_list에서 target값과 같은 원소의 갯수를 리턴한다. 

 

두 번째 코드는 DFS를 재귀적으로 구현한 코드이다.

1. dfs(numbers, target, length, 0)을 호출한다.
2. 인덱스 i가 numbers의 길이인 length와 같다면, numbers의 값이 target과 같은지 확인하고, 같다면 answer의 값을 1 증가킨다.
3. 그렇지 않다면, dfs(numbers, target, length, i+1)을 호출한 뒤, numbers[i]의 값에 -1을 곱한 채로 dfs(numbers,target, length, i+1)을 호출한다. 

이를 그림으로 나타내면 다음과 같다.

편의를 위해 파라미터는 인덱스만 표시했다. 위에서부터 아래로 호출하고, 각 경우에서 각 배열의 합이 target과 같은 경우 전역변수 answer의 값을 1 증가시킨다. 반복적 DFS에서 봤던 그림과는 달리, 이 그림의 각 노드는 하나의 결과값이다. 각 노드가 가지고 있는 NUMBERS배열의 합이 target과 같으면 answer의 값을 1 증가시킨다. 그렇지 않다면, 인덱스를 1 증가시키고, numbers의 i번째 원소를 -1을 곱해서 dfs(i+1)를 호출한다

 

결과

 

 

후기

이 문제로 말할것 같으면, 코테 준비 전에는 하루종일 풀어도 못풀었던 문제였다. 그 당시엔 완전탐색 말고는 아무것도 몰랐는데, 그마저도 for문을 잘 못써서 결국 못풀었다. 사실 지금 푼 것도 다른사람들의 코드를 좀 훔쳐보다가 결국에 완성시킨 답안인데, 그래도 열심히 따라칠건 따라치고 이해할거 이해해서 이렇게 정리해서 게시물을 올리니 정말 마음이 좋다.  그리고, 이 문제가 왜 DFS인지도 몰랐었는데, 문제를 계속 보다보니까 어떻게 dfs를 활용해야할 지 감이 좀 온다.