[알고리즘 문제풀이] 프로그래머스 - 타겟 넘버

yourjin·2022년 3월 25일

BFS DFS level2 알고리즘

알고리즘 문제풀이

목록 보기

22/28

TIL (2022.03.24)

➕ 오늘 푼 문제

프로그래머스 - 타겟 넘버

➕ 아이디어

이 문제의 핵심은 DFS/BFS 유형의 문제라는 것을 알아차리는 것이다.

DFS/BFS는 둘 다 탐색 알고리즘이기 때문에, 조건에 맞는 값을 찾는데도 사용할 수 있다.
이 문제에서 numbers 의 숫자들은 각각 더하거나 빼는 2가지 선택이 가능하다. 이를 해당 숫자를 더한 노드와 뺀 노드를 탐색한다고 이해할 수 있다.
따라서 numbers 의 합, 차로 만들 수 있는 모든 숫자를 그래프로 만들어서, 이 중 조건에 맞는 값을 탐색하는 문제로 바꿔 생각할 수 있다.
- 그래프에서 조건 값을 찾는 문제는 특별한 제한 사항이 없다면 DFS/BFS 모두 구현이 가능하다. 이 문제 또한 DFS/BFS 모두 적용 가능하다.
- 여기서는 재귀 또는 큐(Queue)를 사용하냐의 차이만 있을 뿐, 아이디어에서 큰 차이는 없다.

DFS로 구현하는 방법은 다음과 같다.

→ 함수를 재귀적으로 호출하며, numbers 의 숫자를 방문하고 누적 값을 계산하는 과정을 반복한다.

함수 인자에는 numbers 의 인덱스와 앞서 계산된 누적 값이 포함되어야 한다.
numbers 의 마지막 인덱스 일 때 누적 값이 target 값과 같다면, target을 만드는 1가지 경우의 수를 찾은 것이므로 1을 반환한다. 아니라면 0을 반환한다.
마지막 인덱스가 아닌 경우, 다음 인덱스의 값을 더하고, 뺀 값을 재귀적으로 탐색한다.

BFS로 구현하는 방법은 다음과 같다.

→ 큐(Queue)가 빌 때까지 numbers 의 숫자를 방문하고 누적 값을 계산하는 과정을 반복한다.

큐에는 numbers 의 인덱스와 앞서 계산된 누적 값이 함께 들어가야 한다.
큐에서 이전에 탐색한 인덱스와 누적 값을 꺼낸다.
이 인덱스가 numbers 의 마지막 인덱스 일 때 누적 값이 target 값과 같다면, target을 만드는 1가지 경우의 수를 찾은 것이므로 1을 반환한다. 아니라면 0을 반환한다.
마지막 인덱스가 아닌 경우, 다음 인덱스의 값을 더하고, 뺀 값을 큐에 넣어준다.

➕ Java 코드

DFS 코드

class Solution {
    public int dfs(int[] numbers, int target, int index, int value){
        if(index == numbers.length-1){
            if(target == value){
                return 1;
            }else{
                return 0;
            }
        }
        
        int result = 0;
        
        index += 1;
        result += dfs(numbers, target, index, value - numbers[index]);
        result += dfs(numbers, target, index, value + numbers[index]);
        
        return result;
    }
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, -1, 0);
    }
}

BFS 코드

import java.util.*;

class Item{
    int index;
    int value;
    
    Item(int index, int value){
        this.index = index;            
        this.value = value;
    }
}

class Solution {
    
    public int bfs(int[] numbers, int target){
        int result = 0;
        Queue<Item> queue = new LinkedList<Item>();
        queue.add(new Item(-1, 0));
        
        while(!queue.isEmpty()){
            Item item = queue.poll();
            
            if(item.index == numbers.length-1){
                if(item.value == target){
                    result += 1;
                }
                continue;
            }
            
            int index = item.index+1;
            queue.add(new Item(index, item.value-numbers[index]));
            queue.add(new Item(index, item.value+numbers[index]));
        }
        
        return result;
    }
    
    public int solution(int[] numbers, int target) {
        return bfs(numbers, target);
    }
}

➕ Python 코드

DFS 코드

def dfs(numbers, target, index, value):
    if len(numbers)-1 == index:
        if target == value:
            return 1
        else:
            return 0
    
    index += 1
    minus_value = dfs(numbers, target, index, value - numbers[index])
    plus_value = dfs(numbers, target, index, value + numbers[index])
    
    return minus_value + plus_value
    
def solution(numbers, target):
    return dfs(numbers, target, -1, 0)

BFS 코드

from collections import deque

def bfs(numbers, target):
    answer = 0
    queue =  deque([(-1,0)])
    index = 0
    
    while queue:
        index, value = queue.popleft()
        
        if index == len(numbers)-1:
            if value == target:
                answer += 1
                
            continue
        
        index += 1
        queue.append((index, value+numbers[index]))
        queue.append((index, value-numbers[index]))
    
    return answer

def solution(numbers, target):
    return bfs(numbers, target)

➕ 궁금한 내용 및 소감

처음에 이 문제를 어떤 식으로 접근해야 할 지 감이 안와서 다른 분의 풀이를 참고했다. 단순한 구현 문제라고 생각했는데, 이를 그래프로 생각할 수 있다는 게 굉장히 놀라웠다! 한편으로 이 사고가 익숙해지기만 한다면 아이디어를 구현하는 건 그렇게 어렵지 않을 것 같다는 생각도 들었다. BFS/DFS 문제들은 좀 더 많은 문제를 풀어 유연한 사고가 가능하도록 하는 것이 중요할 것 같다.