[프로그래머스]타겟 넘버

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

프로그래머스

풀이

dfs/bfs문제였는데 이번에는 dfs로 풀어봤다. 그래프에는 bfs가 좋지만, 이런 문제에는 재귀가 더 쉬운 것 같다. 구현 자체는 어렵지 않았지만, 헷갈린 점이 매 재귀마다 for문을 돌려야할줄 알았다. 생각해보니 그냥 반복문 없이 인덱스만 하나씩 이동하면서 visited을 확인하고 백트래킹하면 가능한 경우의 수를 구할 수 있다. visited는 visited[len(numbers)][2]로 해주었고, 2는 더했는지/뻈는지 여부 확인용이다. 

def dfs(x, visited, i, number, target):
        global answer
        if i == len(number) -1:
            if not visited[i][0]:
                if x + number[i] == target:
                    answer += 1
            if not visited[i][1]:
                if x - number[i] == target:
                    answer += 1
            return
        if not visited[i][0]:
            visited[i][0] = True
            dfs(x+number[i], visited, i+1, number, target)
            visited[i][0] = False
        if not visited[i][1]:
            visited[i][1]= True
            dfs(x-number[i], visited, i+1, number, target)
            visited[i][1] = False
def solution(numbers, target):
    global answer
    answer = 0
    visited = [[False, False]for _ in range(len(numbers))] #더했는지, 뺐는지 방문 확인 여부
    dfs(0, visited, 0, numbers, target)
    return answer