DFS문제 풀이 - 타겟 넘버

게임 맵 최단거리 문제

최근에 프로그래머스에서 카카오 ‘게임 맵 최단 거리’ 라는 문제를 풀다가 이게 DFS로 풀어야할지 BFS로 풀어야할지 고민을 하다 그렇다면 ‘어떤 문제를 DFS로 풀고 어떤 문제를 BFS로 풀어야할까?’ 라는 생각이 들어 이 둘을 더 알아보고, 이런 유형의 문제도 더 풀어보기로 했다.

Tip

위와 같은 문제인 최단 거리 문제는 보통 BFS를 이용하여 푸는 것이 적절하다.

그 이유는 DFS로 목적지까지 도달하는 경우 최단거리라는 보장이 없기 때문에 모든 경우를 다 탐색해야하는데 반해, BFS로 목적지에 도달하는 경우에는 그 첫 도달경로가 최단거리이기 때문에 더 탐색할 필요가 없다.

---

그래서 풀어본 문제는 프로그래머스에 있는 문제인 ‘타겟 넘버’이다.

문제 링크

문제 설명

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 함수를 작성해주세요.

문제 접근

• 뒤에 어떤 숫자가 어떤 부호로 나올지 모르기 때문에 그냥 모든 경우를 탐색해야할 것 같다.

• 순서가 고정되어 있고 부호는 더하기와 빼기밖에 없다. 그리고 제한사항의 numbers의 길이가 20을 넘지 않기 때문에 모든 경우를 탐색해도 2²⁰(더하기 or 빼기를 20번 반복) = 약 100만 이기 때문에 무리한 연산없이 수행할 수 있다.

• DFS나 BFS 어떤 방법을 써도 상관없을 것 같다. 나는 익숙한 DFS를 사용하였다.

풀이 코드

def solution(numbers, target):
    global length, count
    length = len(numbers)
    ## print("길이",length)
    result = 0
    count = 0
    recursion(0,result, numbers, target)
    print("카운팅",count)
    return count

def recursion(depth, result , nums, target):
    global count
    ## print(depth, result)
    if depth == length: # 마지막 계산
        ## print("in")
         # target 과 같으면 카운팅           
        ## print('타겟:',target,"결과",result)
        if target == result:
            count += 1
        return

    recursion(depth+1, result + nums[depth] , nums, target)
    recursion(depth+1, result - nums[depth] , nums, target)

DFS 풀이 정리(재귀 함수)

• 파라미터로 들어가야할 것을 정한다.
  • 파라미터로 꼭 들어가야 할 것: 탐색하면서 깊이에 따라 변하는 것 ex) 깊이, 지나온 경로
  • 꼭 들어가지 않아도 될 것: 탐색하면서 변하지 않는 것 ex) target, numbers + 재귀함수 내에서 필요한 경우 전역으로 선언하여 사용하거나 파라미터로 넘겨 사용할 수 있다.(참조값을 넘겨주는 것이라서 부담 없음)

• 도달점에서 해야할 로직을 작성한다.

• 첫 시작점과 끝점의 로직을 잘 확인하여 빠지는 부분없이 잘 탐색하는지 확인한다.

개선점

처음 방법으로, 파라미터로 계산된 수가 아닌 문자열 전체를 넘기고 마지막 깊이에 도달했을 때 한번에 계산하는 방법을 사용하였다.

하지만 이때 부호와 숫자로 경우를 나누다가, 숫자를 한 덩어리로 잘못 생각하여 두자릿 수 이상을 잘못 연산하였다. 하필 예제 케이스도 모두 한자릿 수라서 어느 부분이 잘못됐는지 거의 1시간 정도 찾은 것 같다..

숫자를 형변환할 때 항상 조심하고 잘 됐는지 확인하자!