[DFS/BFS] 타겟 넘버 - Python

 

코딩 테스트 준비과정에서 글을 작성해 봅니다.

모두가 많이 사용하는 Programmers의 문제들을 풀면서 스스로 얻은 과정들을 공유하고자 합니다.

 

이번에 풀어볼 문제는 트리 탐색문제중 하나인 타겟 넘버입니다.

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

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

 

 

문제는 링크에 적혀있으므로 생략하겠습니다.

 

배열의 원소마다 +,- 를 결정하여 선택하기 때문에 일종의 이진트리와 같습니다.

 

이 때 이진 트리의 말단 부 중 타겟 넘버가 말단 노드가 되는 루트의 개수를 반환하면 되는 문제입니다.

 

 

1. BFS (너비 우선 탐색)

 

말 그대로 너비를 우선해서 탐색하는 방식입니다. 그림을 보면 이해가 쉽습니다.

BFS의 예시, Wikipedia

이번 문제에서는 이 방식을 사용합니다.

 

단계를 진행 할 수록 배열에서 값을 꺼내서 + / - 여부를 선택하여 모든 트리를 완성하면 됩니다.

 

이를 위해서 먼저 queue를 사용하는 것을 알아볼 필요가 있습니다.

 

 

2. Python의 queue

 

파이썬에서 queue를 사용하는 방법은 크게 두 가지가 있습니다.

 

 

 2.1) list 를 이용한 queue 

data = list([1,2,3,4])

 위와 같은 방식을 사용하면 pop, append를 이용하여 배열에 가장 끝에서 값을 꺼내거나 붙일 수 있습니다.

 혹은 insert 함수를 사용하여 원하는 위치에 원소를 넣고 나머지 원소를 뒤로 밀어버릴 수 있습니다.

 

data.pop() 		# 4가 나온다
data.append(x) 		# x값을 가장 끝에 붙인다
data.insert(0, x)	# 0번째 자리에 x값을 넣는다

 

 2.2) deque 를 이용한 큐

 

 모듈을 이용하여 큐를 사용할 수 있습니다. 이 때는 붙이는 방향을 선택할 수 있기때문에 훨씬 유용하며 

 결정적으로 원소를 Shift 하는 과정이 pop, append등에 있기 때문에 deque 에서 사용하는 함수가 훨씬

 성능적으로 빠른 속도를 가지고 있습니다.

 

from collections import deque

queue = deque([x, y])

queue.popleft() 	# 앞에서 원소를 꺼냄
queue.pop()		# 뒤에서 원소를 꺼냄

queue.append()  	# 뒤에서 원소를 붙임
queue.appendleft() 	# 앞에서 원소를 붙임

 

 마지막으로 Queue를 사용한 방법도 있으며 이는 멀티쓰레딩시 유용하지만 방향성이 없으므로 이번 문제에서는 사용하기 곤란한 방식입니다.

 

 문제를 해결하기 위해서 2번째 deque를 이용하여 문제를 풀어보도록 하겠습니다.

 

 

3. 문제 풀이

 

일종의 이진트리를 만들어서 문제를 해결합니다. 

 

from collections import deque

def solution(numbers, target):
    
    answer = 0
    queue = deque([(0,0)])
    
    
    
    return answer

 

(0, 0) 을 첫 원소로 하는 queue를 생성합니다.

이 때 앞에 있는 0은 지금까지 이어진 원소의 합,

 

뒤의 0은 트리의 깊이 즉 지금까지 더한 원소의 값을 의미하며

뒤 0 값이 numbers 의 길이에 도달하고 target과 같은 경우 answer를 하나 증가시키는 것으로 알고리즘을 작성하면 됩니다.

 

while queue:
        
        Sum , level = queue.popleft()
                      
        if level > len(numbers):
            break
            
        elif level == len(numbers) and Sum == target:
            answer += 1
        
        queue.append(((Sum + numbers[level - 1]), level + 1))
        queue.append(((Sum - numbers[level - 1]), level + 1))

 

먼저 중단 조건인 level 이 주어진 배열의 길이와 같을 때 중지하는 조건문을 먼저 넣습니다.

 

그리고 두 번째 조건으로 level 값이 최대 길이 수이며 Sum (지금까지의 더하거나 뺀 값) 이 target 값과 같을 때 

카운트를 하나 증가시킵니다.

 

이후 양 방향 즉 level은 같지만 

number의 원소를 더하거나 뺀 값을 각각 순서대로 append 함으로써 트리를 채워나갑니다.

 

위 알고리즘의 진행 사항은 다음과 같습니다.

 

numbers = [1,1,1,1,1] target = 3 일 때

 

1) 최초 Sum 값 Level 값이 0,0 인 트리 생성

2) 반복문 입장

3) (Sum = 0, level = 0) => 최초 numbers 원소 1을 각각 더하거나 뺀 값을 append

 (1, 1) (-1, 1) 인 큐

4) popleft 로 (1,1) 을 꺼낸다

5) 3번과 마찬가지로 두 번째 원소 1을 꺼내어 더하거나 뺌

 (-1, 1) (2, 2) (1, 2) 인 큐 

6) 3 - 5번 과정을 len(numbers) == 5 보다 커질때 까지 반복하면 트리가 완성

7) 이 때 level 값이 5 and tartget == Sum 인 경우 answer에 1을 더해 줌

8) 6 번 과정을 하나라도 만날 경우 stop 

  => 이 때 이미 큐에는 (4,6) 등의 형식으로 level이 6인 말단 노드들 만이 남음

 

최종 코드 

 

from collections import deque

def solution(numbers, target):
    
    answer = 0
    queue = deque([(0,0)])
    
    while queue:
        
        Sum , level = queue.popleft()
                      
        if level > len(numbers):
            break
            
        elif level == len(numbers) and Sum == target:
            answer += 1
        
        queue.append(((Sum + numbers[level - 1]), level + 1))
        queue.append(((Sum - numbers[level - 1]), level + 1))
    
    
    
    return answer

 

 

결론

 

굉장히 짧은 코드로 마무리되었지만 생각하는데 굉장히 오랜시간이 걸렸습니다.

연습을 더해야겠네요