[알고리즘] 타겟 넘버

프로그래머스_타겟 넘버

문제 풀이에 앞서 DFS와 BFS를 살펴보면 좋다.

살펴보기에 앞서 그래프에 대해 간단히 살펴보자.

그래프
정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말한다.
더 나아가 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

DFS
Depth First Search, 깊이 우선 탐색

깊이 우선 탐색은 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.
(주로 스택 혹은 재귀호출을 통해 그래프를 순회하는 방법이다.)

BFS
Breadth First Search, 너비 우선 탐색

너비 우선 탐색은 루트노드에서 시작하여 인점한 노드를 먼저 탐색하는 방법으로 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방식이다.
(주로 큐를 이용하여 그래프를 순회하는 방법이다.)

출처 https://namu.wiki/w/BFS

DFS를 이용한 풀이

def solution(numbers, target):
	answer = 0
    answer += DFS(numbers, target, 0)
    return answer
def DFS(numbers, target, depth):
	answer = 0
    if depth == len(numbers):
    	if sum(numbers) == target:
        	return 1
        else: return 0
    else:
    	answer += DFS(numbers, target, depth + 1)
        numbers[depth] *= -1
        answer += DFS(numbers, target, depth + 1)
        return answer

완전 탐색을 위해 루트 노드에서 마지막 노드 즉 최종 노드에 도착했다면 numbers를 모두 더한 값을 목표 값과 비교하여 문제를 해결하였다.

BFS를 이용한 풀이

def solution(numbers, target):
	answer = 0
    Arr = [0]
    for num in numbers:
    	tmp = []
        for arrNum in Arr:
        	tmp.append(arrNum + num)
            tmp.append(arrNum - num)
         Arr = tmp
     for arrNum in Arr:
     	if arrNum == target:
        	answer += 1
     return answer

루트노드와 인접한 노드를 먼저 탐색하기 위해 numbers의 값을 더하고 뺀경우를 큐에 저장함으로써 모든 계산 결과 값이 담기게 된다. 이를 target과 비교하여 문제를 해결하였다.