[프로그래머스, 파이썬] 타겟 넘버 - 레벨 2 | 깊이/너비 우선 탐색(DFS/BFS)

📌 프로그래머스 Level 2 : 타겟 넘버

고득점 키트 깊이/너비 우선 탐색(DFS/BFS)에서 가장 난이도가 쉬운 '타겟 넘버' 문제이다.

DFS로 푸는 문제인데, DFS와 BFS의 기본 구조를 모르면 헤맬 수 있다.

<내 답안>

def solution(numbers, target):
    sum = 0
    cnt = 0
    answer = 0
	def dfs(cnt,sum):
        nonlocal answer
        if cnt == len(numbers)-1:
            if sum+numbers[cnt] == target:
                answer+=1
            if sum-numbers[cnt] == target:
                answer+=1
            return answer
        dfs(cnt+1,sum+numbers[cnt])
        dfs(cnt+1,sum-numbers[cnt])
    dfs(cnt,sum)
    return answer

<답안 설명>

def solution(numbers, target):
    sum = 0
    cnt = 0
    answer = 0
    #dfs 구현
    #cnt = 재귀함수를 멈춰줄 count, sum = 재귀함수 돌면서 합한 값
    def dfs(cnt,sum):
        #nonlocal 사용해야 answer 변수 공유 가능
        nonlocal answer
        #함수가 numbers 끝까지 탐색했을 때
        if cnt == len(numbers)-1:
            # numbers의 마지막 값을 더하고 빼서 최종 sum 구하고
            # 그 값이 target 값과 같으면 answer += 1
            if sum+numbers[cnt] == target:
                answer+=1
            if sum-numbers[cnt] == target:
                answer+=1
            # 그리고 return해서 answer 값 반환
            return answer
        # 재귀함수, cnt를 +1 해줌으로써 numbers 배열 끝까지 돌 수 있도록
        dfs(cnt+1,sum+numbers[cnt])
        dfs(cnt+1,sum-numbers[cnt])
    dfs(cnt,sum)
    return answer

아래와 같이 함수를 따로 빼서 풀 수도 있다.

단 위와 같은 풀이와 다르게 외부에 함수를 만들면, numbers와 target 변수를 공유할 수 없어서 직접 써줘야하는 번거로움이 있다.

그리고 어떤 코딩마스터 슨배님에 의하면.. 외부로 따로 빼서 함수를 구현하면 더 시간이 많이 걸린다고 한다.

<답안2>

def dfs(numbers,cnt,sum,target):
    global answer
    if cnt == len(numbers)-1:
        if sum+numbers[cnt] == target:
            answer+=1
        if sum-numbers[cnt] == target:
            answer+=1
        return answer
    dfs(numbers,cnt+1,sum+numbers[cnt],target)
    dfs(numbers,cnt+1,sum-numbers[cnt],target)
def solution(numbers, target):
    # global 변수 지정해주고, 사용할 함수 안에 다시 global answer로 불러내줘야함
    global answer
    answer = 0
    sum = 0
    cnt = 0
    dfs(numbers,cnt,sum,target)
    return answer

이 문제는 워낙 단순해서 그런지 별 차이는 보이지 않는다.

확실히 답안2가 더 느린 것 같기도..

DFS는 재귀함수를 많이 사용하는데, 대략적인 DFS 코드 구현 틀을 잡고있으면 문제를 풀 때 좋은 것 같다.

내가 자주 사용하는 DFS의 큰 뼈대는 다음과 같은데,

def dfs(start,cnt,~~~):
    1. 재귀를 중단하고 값을 반환할 조건
    if cnt == ~~~:
        return ~~~
    2. 재귀함수
    dfs(start,cnt+1,~~~)

더 좋은 방법도 있겠지만 아직 코린이인 나는..🥲

아무튼 이 문제는 DFS를 처음 구현해보고 이해하기에 좋았던 것 같다!

몇 달 쉬었다고 완전히 감을 잃었지만 다시 많이 많이 풀어봐야겠다!😃