[파이썬] 프로그래머스_타겟 넘버(DFS/BFS)

문제

 

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

코딩테스트 연습 - 타겟 넘버

 

---

해설

 

DFS/BFS 문제는 항상 잘 못푸는데,

이 문제 역시 다른 코드를 보고 나서야 어떻게 풀어야 하는지 감을 잡았다..

 

이 문제는 numbers 배열에 담긴 숫자들을 더하거나 / 빼서

target과 같은 값이 나오도록 만드는 방법의 수를 구하는 문제이다.

 

그럼 우선 더하기 / 빼기 밖에 없으니 직접 해보면 된다.

numbers : [1,1,1,1,1]

target : 3일 때를 그려보면 아래와 같이 나온다.

위와 같은 계산을 numbers의 숫자 개수만큼 5번 하면 된다.

결국엔 모든 계산을 배열(res)에 저장해서 배열 안의 각 숫자가 target과 같은지 비교하면 끝이다.

 

아직 DFS로 구현하는 방법은 하지 못했다.

아래는 BFS 구현 코드이다.

 

만약 위의 설명을 봐도 이해가 안된다면 아래 정답 코드를 IDE에 복사해가서 

print(solution([1,1,1,1,1], 3))을 적고 직접 디버거를 돌려보길 추천한다.

직접 보면 이해가 훨씬 빠르다.

---

코드

 

-파이썬(BFS)

def solution(numbers, target):
    answer = 0  #타겟 넘버를 만드는 방법의 수
    res = [0]  #타겟과 비교할 수를 넣을 배열 -> 처음 계산을 해야하니 초기값 필요
    
    for i in numbers:
        tmp = []  #한 사이클 결과값 임시 저장 배열
        for j in res:
            tmp.append(j + i)
            tmp.append(j - i)
        res = tmp  #임시 저장 배열 res에 넣어주기
    
    for i in res:
        if i == target:  #타겟과 res[i]값 비교
            answer += 1
    
    return answer