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

알고리즘 고득점 키트 BFS/DFS lv2 타겟넘버

 

숫자 배열이 주어지고, 목표 값이 있음

각 숫자를 더하거나 빼서 목표 값을 만들고, 총 목표 값을 몇 가지로 만들 수 있는지 return하면 됨

 

혼자 못풀었음

풀이 참고함

 

BFS 풀이

 

모든 연산을 저장하는 leaves 배열이 존재

for문을 돌며 각 숫자를 탐색

    leaves 안에 있는 모든 숫자들에 대해서, 현재 숫자를 더하거나 뺀 값을 임시 배열에 저장함

    leaves 배열 값을 임시 배열값으로 치환함

   #어차피 숫자 순서를 바꾸거나 하는 일은 없으니까

   #순서대로 각 숫자를 더하거나 뺐을 때 경우를 다 저장해서 나중에 target 값인지만 확인하면 됨

 

for문 돌며 leaves안에 있는 값 살펴봄. target값이면 answer +1

 

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

 

 

DFS 풀이

 

일단 depth 0에서 시작해서, depth를 증가시켜가며 재귀함수를 실행함

depth가 numbers 길이와 같아지기 전까지, 각 numbers의 요소에 -1을 곱한 값을 재귀함수에 계속 집어넣음

 -> 각 자리에 부호를 + 또는 -로 직접 실험해보는 것과 같음

계속 그렇게 배열을 만들다가, depth가 numbers의 길이와 같아지면

-> 각 자리에 부호를 집어넣는 작업을 다 끝냈다는 뜻, 그럼 모든 숫자의 합을 구해서 target값이랑 일치하는지 비교

-> 일치하면 answer에 더해줄 값을 1로 return 아니면, answer에 더해줄 값을 0으로 return

 

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

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

 

 

 

참고 출처

https://velog.io/@timointhebush/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84-DFS-BFS-Python