[프로그래머스 | 파이썬 / 자바스크립트] 타겟 넘버(깊이/너비 우선 탐색(DFS/BFS)/level 2)

문제

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

프로그래머스

 

 

🐍파이썬

def solution(numbers, target):
    answer = [0]
    for i in numbers:
        sub = []
        for j in answer:
            sub.append(j-i)
            sub.append(j+i)
        answer = sub
    return answer.count(target)

Example
numbers = [1, 1, 1, 1, 1]
target = 3 일 때,

i = 1
sub = []
j = 0
sub.append(0 - 1)
sub.append(0 + 1)
answer = [-1, 1]

i = 1
sub = []
j = -1
sub.append(-1 - 1)
sub.append(-1 + 1)
j = 1
sub.append(1 - 1)
sub.append(1 + 1)
answer = [-2, 0, 0, 2]

i = 1
sub = []
j = -2
sub.append(-2 - 1)
sub.append(-2 + 1)
j = 0
sub.append(0 - 1)
sub.append(0 + 1)
j = 0
sub.append(0 - 1)
sub.append(0 + 1)
j = 2
sub.append(2 - 1)
sub.append(2 + 1)
answer = [-3, -1, -1, 1, -1, 1, 1, 3]

... 이하 생략
위와 같이 하나의 노드에서 가지를 뻗어가며 +했을 때의 결과와 -했을 때의 결과를 모두 구한다.
모든 과정이 끝났을 때 answer 안에 target 값이 몇 개나 들어있나를 체크해 타겟 넘버를 만드는 경우의 수를 구할 수 있다. 

풀이 방법은 아래 블로그를 참고했다.

https://tinyurl.com/2jveb9om

[ Programmers ] level 2 - 타겟 넘버 ( python )

 

 

다른 풀이 방법

DFS

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

---

answer = 0
def DFS(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if(idx == N and target == value):	#종료조건
        answer += 1
        return
    if(idx == N):	#종료조건
        return
    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])

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

---

BFS

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

---

def solution(numbers, target):
    answer = 0
    queue = [(0, 0)]
    length = len(numbers)

    while queue:
        n = queue.pop()
        if n[0] < length:
            queue.append((n[0] + 1, n[1] + numbers[n[0] - 1]))
            queue.append((n[0] + 1, n[1] - numbers[n[0] - 1]))
        elif n[1] == target:
            answer += 1

    return answer

 

 

🐥자바스크립트

function solution(numbers, target) {
    var answer = 0;
    function DFS(idx, result){
        if(idx === numbers.length){	//종료조건. numbers의 끝까지 탐색했을 시
            if(result === target){	//result가 target과 동일하면 answer++진행 후 리턴
                answer += 1;
            }
            return	//target과 result가 같지 않을 때는 그냥 리턴
        }
        DFS(idx+1, result - numbers[idx]);	//노드에서 빼기 부분으로만 dfs
        DFS(idx+1, result + numbers[idx]);	//노드에서 더하기 부분으로만 dfs
    }
    DFS(0,0);	//시작인덱스와 시작result값을 dfs함수에 대입해준다.
    return answer;
}

풀이 방법은 아래 블로그를 참고했다.

https://tinyurl.com/2pcrak22

[Python] 프로그래머스 level2 타겟넘버 (BFS/DFS)

dfs, bfs 어렵다...

 

 

 

참고할 만한 블로그

 

https://tinyurl.com/2med2apc

프로그래머스 - 타겟 넘버 (DFS, BFS) Python