[프로그래머스 Lv.2] 타겟 넘버(DFS/BFS)

[프로그래머스 Lv.2] 타겟 넘버(DFS/BFS)

파이썬 풀이

(1) DFS 풀이

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    def dfs(value, idx):
        if idx == n:
            if value == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(value + numbers[idx], idx + 1)
            dfs(value - numbers[idx], idx + 1)
    dfs(0, 0)
    return answer

• dfs(i)로 dfs(i - 1)과 dfs(i + 1)을 호출
• idx가 numbers 길이와 같아지면 종료
  • 이때 target과 결과값이 같으면 count 증가 후 종료
  • 같지 않으면 그냥 종료

(2) BFS 풀이 - deque 사용

from collections import deque
def solution(numbers, target):
    answer = 0
    n = len(numbers)
    queue = deque()
    queue.append([numbers[0], 0])
    queue.append([-numbers[0], 0])
    while queue:
        temp, idx = queue.pop()
        idx += 1
        if idx >= n:
            if temp == target:
                answer += 1
        else:
            queue.append([temp + numbers[idx], idx])
            queue.append([temp -numbers[idx], idx])
    return answer

(3) BFS 풀이 - stack 사용

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    queue = [[numbers[0], 0], [-numbers[0], 0]]
    while queue:
        temp, idx = queue.pop()
        idx += 1
        if idx >= n:
            if temp == target:
                answer += 1
        else:
            queue.append([temp + numbers[idx], idx])
            queue.append([temp -numbers[idx], idx])
    return answer

자바 풀이

(1) DFS 풀이

class Solution {
    int answer = 0; // 전역 변수로 선언
    
    public void dfs(int value, int idx, int[] numbers, int target){
        if(idx == numbers.length){
            if(value == target){
                answer += 1;
            }
        }
        else{
            dfs(value + numbers[idx], idx + 1, numbers, target);
            dfs(value - numbers[idx], idx + 1, numbers, target);
        }
    }
    
    public int solution(int[] numbers, int target) {
        dfs(0, 0, numbers, target);
        return answer;
    }
}

(2) BFS 풀이 - Queue

import java.util.*;

class Pair{
    int temp;
    int index;
    Pair(int temp, int index){
        this.temp = temp;
        this.index = index;
    }
}

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        int n = numbers.length;
        
        Queue<Pair> q = new LinkedList<Pair>();
        
        q.offer(new Pair(numbers[0], 0));
        q.offer(new Pair(-numbers[0], 0));
        
        while(!q.isEmpty()){
            Pair p = q.poll();
            p.index += 1;
            if(p.index >= n){
                if(p.temp == target){
                    answer += 1;
                }
            }else{
                q.offer(new Pair(p.temp + numbers[p.index], p.index));
                q.offer(new Pair(p.temp - numbers[p.index], p.index));
            }
        }
        return answer;
    }
}

• Pair 클래스를 따로 만들어서 큐에 값과 인덱스를 함께 저장하도록 함