프로그래머스 그래프탐색(1): 타겟 넘버

 

오늘 하루를 들여 DFS/BFS를 제대로 이해해보자는 목표를 잡았었다. 그래도 머리 좀 굴리다보니까 이해를 못한것같지는 않았는데 그럼 오늘 푼 문제 복습겸 프로그래머스 한 번 들어가볼까~ 했다가 울뻔했음 ㅎ... DFS/BFS 카테고리에 포함된 문제가 아니었다면 무지성 완전탐색 돌려서 sum으로 때려맞추고 시간초과 판정 받지 않았을까 싶다. 분류로부터 답을 역산하는 이상한 방법(...)으로 어찌저찌 문제를 풀긴 풀었다. 효율성 등 부족한 부분이 많겠지만 나름대로 이 문제를 풀며 했던 생각의 흐름을 정리해보고자 이렇게 포스팅을 남긴다.

 

def make_graph(numbers, target):
    n = len(numbers) + 1
    graph = [[] for _ in range(n)]
    graph[0].append(target)
    for i in range(n):
        for node in graph[i]:
            if i == (n-1):
                break
            graph[i+1].append(node + numbers[n -2 -i])
            graph[i+1].append(node - numbers[n -2 -i])
    return graph

def solution(numbers, target):
    graph = make_graph(numbers, target)
    count = graph[-1].count(0)
    return count

핵심 로직은 맞는것같은데 코드 상태가...ㅎ

append 안쓰고 재귀로 풀어보려다 재귀함수 짤 머리가 안돌아가서 그냥 편한 길(?)을 선택했다.

 

(1) 일단 리턴값인 target이 어떠한 과정을 통해 나오는지부터 생각해보았다. 각 number마다 주어진 선택지는 해당 수를 더하거나, 빼거나니까 target은 결국 numbers[-1]을 더하거나 빼서 나온 결과값이다. 그러면 target에 도달하기 이전의 이 수는 target + numbers[-1]이거나 target - numbers[-1]이거나 둘 중 하나였을 것이다.

 

(2) 만일 (1)의 과정을 numbers 배열의 횟수만큼 반복한 뒤 나온 결과가 0이라면, 해당 요소가 0이 되기까지 거쳐온 과정을 뒤집으면 0에서 target 숫자에 이르는 루트에 해당할 것이다.

 

(3) 따라서 노드들을 단계별로 구분하여 리스트에 집어넣고 리스트의 마지막 단에서 나온 0의 갯수를 세면 문제에서 요구하는 return값(target에 도달하는 경로의 수)을 구할 수 있다

 

그래도 그래프 처음보는 사람치고 괜찮지 않나 ㅎㅎ 다른사람들 코드 보니까 진짜 신기하게 잘 풀었던데 밤이 늦어서 졸린바람에 아직 제대로 보진 못했다. 내일 천천히 보면서 공부해봐야지...

 

 

 

(+)

 

수도코드와 각 변수처리를 제대로 하기 전까지는 그냥 코드에 손을 대질 말아야겠다.

쓰면서 생각하니까 정신도 없고 이러다 에러 한번 나면 어찌할줄을 모르고 안절부절함.

또, 긴가민가하면 금방 답 보고싶어서 안절부절하는 버릇도 고쳐야지.

알고리즘은 원래 누구나 어려운게 맞는데 나는 쓸데없이 너무 조급해하는것같다.

빨리 동빈북으로 개념 다 떼고 프로그래머스에서 유형별로 문제풀이 조금씩 하면서 파이썬 알고리즘 인터뷰로 넘어가야겠으~