TIL - algorithm - 너비 우선 탐색(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 함수를 작성해주세요.

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예제

풀이(이중 for loop 활용)

• 경우의 수를 모두 구하는 문제다. 처음 접근했던 풀이 방법은 이중 for loop를 사용하는 것이었고, 다음과 같은 코드로 어찌저찌 문제를 풀 수 있었다.

• 풀이에 대해 간단히 설명하자면, 첫 번째 for loop로 주어진 배열 numbers의 요소를 순회시키고, 두 번째 for loop에서 순회하는 요소를 더할 경우의 값과 뺄 경우의 값을 각각 구한 후, 새로 생성한 배열에 담는 것이었다. 이러한 방식으로 배열 numbers를 전부 순회하고 나면, 총 5회(len(numbers)의 길이)에 걸쳐 연산이 이뤄진 모든 결괏값이 담긴 배열이 만들어진다.

def solution(numbers, target):
    answer = 0
    number_of_cases = [0]

    for num in numbers:
        calculate_result = []
        for case in number_of_cases:
            calculate_result.append(case+num)
            calculate_result.append(case-num)        
        number_of_cases = calculate_result

    for case in number_of_cases:
        if case == target:
            answer += 1

    return answer

• 하지만 이러한 풀이법은 문제가 의도하는 깊이/너비 우선 탐색(DFS/BFS)을 응용하지 않았다는 점에서 한계가 있을 수밖에 없다. 그래서 DFS/BFS를 활용한 풀이를 해보기로 했다. 필자의 경우, 너비 우선 탐색(BFS)을 활용했으므로, 너비 우선 탐색에 대해서만 다루도록 하겠다.

너비 우선 탐색(BFS)이란?

• BFS의 개념을 간단히 살펴보면 아래와 같다.

  • 시작 정점(루트 노드, 혹은 다른 임의의 노드)으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

  • 자세한 설명은 이곳을 참고하면 된다: 참고 사이트

• BFS의 특징

  • 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

    • 즉, 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.

  • 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

    • Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
    • 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
    • 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

  • BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.

    • 즉, 선입선출(FIFO) 원칙으로 탐색
    • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

풀이(BFS)

• 우선 자료 구조 queue를 활용해야 하므로, 모듈 deque를 활용해 queue 객체를 만들어주자.

• 요소를 튜플 형태로 만드는 까닭은, 경우의 수(덧셈과 뺄셈 연산으로 얻어진 노드)의 level(깊이)을 나타내기 위함이다.

  • 노드의 level이 len(numbers)와 일치한다는 것은, 해당 노드가 numbers의 모든 요소를 더하거나 빼서 얻어진 결괏값임을 의미하기 때문이다.

  • level은 numbers의 요소를 꺼내는 인덱스로도 사용된다는 점을 주의하자!

    • 즉, IndexError가 발생하지 않도록 예외처리에 신경써야 한다는 뜻이다.

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque([(0,0)]) # sum, idx(level)

    return answer

• 다음으로, 선입선출(FIFO) 원칙에 따라, queue의 첫 번째 요소를 꺼내자. 이때, 꺼낸 요소(튜플 형태)는 unpacking으로 각각 변수 num_sum과 idx에 할당한다.

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque([(0,0)]) # sum, idx(level)
    
    num_sum, idx = queue.popleft()

    return answer

• queue 객체의 요소가 모두 제거(out)되어 비어있을 때까지 순회가 계쏙되어야 하므로 while queue:로 loop를 만들어 준다.

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque([(0,0)]) # sum, idx(level)
    
    while queue:
        num_sum, idx = queue.popleft()
        
    return answer

• 이제, idx를 이용하여 numbers의 요소를 차례대로 꺼낸후, 해당 요소를 queue에서 제거된 요소에 더하거나 뺀 값을 생성한 뒤, queue 객체에 추가(in)한다.

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque([(0,0)]) # sum, idx(level)
    
    while queue:
        num_sum, idx = queue.popleft()
        
        num = numbers[idx]
        
        queue.append((num_sum + num, idx + 1))
        queue.append((num_sum - num, idx + 1))

    return answer

• 여기까지 완성되면 queue 객체 안에는, 각각의 level에 해당하는 모든 경우의 수가 추가되고, 제거되는 작업이 반복된다. 언제까지? numbers[idx]에서 IndexError가 발생할 때까지이다.

• 남은 작업은 크게 두 가지다. 하나는 queue의 요소가 level이 5인 경우에, num_sum이 target과 일치하는 지를 확인하여 answer값을 증가시키는 것. 다른 하나는 numbers[idx]에서 IndexError가 발생하지 않도록 예외 처리를 하는 것이다. 다양한 방식이 있을 수 있는데, 필자는 아래와 같이 처리했다.

• continue를 활용하면, queue 객체에 더 이상, 추가(in)는 이뤄지지 않고, 출력(out)만 이뤄지게 된다.

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque([(0,0)]) # sum, idx(level)

    while queue:

        num_sum, idx = queue.popleft()

        if idx == len(numbers):
            if num_sum ==target:
                answer += 1
                continue
            else:
                continue

        number = numbers[idx]

        queue.append((num_sum + number, idx+1))
        queue.append((num_sum - number, idx+1))

    return answer

reviews

• 자료 구조 Queue 활용 방법을 간단하게 일반화하면 다음과 같다.
  1. Queue 자료 구조의 첫 번째 값을 제거(out)
  2. 출력된 값을 문제에서 요구하는 바에 따라 처리
  3. 처리한 값을 Queue 자료 구조에 추가(in)
  4. Queue 자료 구조의 모든 요소가 제거될 때까지 위 작업을 반복

def solution(numbers,target):
    result = {0: 1}
    
    for number in numbers:
        temp_result = {}
        for num, count in result.items():
            temp_result[num+number] = temp_result.get(num+number, 0) + count
            temp_result[num-number] = temp_result.get(num-number, 0) + count
            
        result = temp_result
        
    return result.get(target)