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

 

 

 

 

---

1. 문제 출처

---

문제 경로 : 코딩테스트 연습 > 깊이/너비 우선 탐색 > 타겟넘버

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

1. 타겟 넘버

 

---

2. 설계 및 코드

---

 

방법1) DFS

DFS는 시스템 스택을 사용하는 방법이다.

 

변수 설명

* numbers : 정답을 도출하기 위한 숫자들의 집합

* target : numbers로 도출해야 하는 정답

* idx : numbers 어느 숫자에 접근해야 하는지 나타내는 인덱스

* cur : 현재 numbers로 계산된 숫자 (target을 도출하기 위한 과정이라고 볼 수 있음)

 

 

- DFS 함수 파라미터에 numbers, target, idx, cur을 받는다.

- 각 idx에 따라 +와 - 두 갈래의 길이 있다.

 

ex) numbers = [1,2,3,4], target = 10 라고 한다면

result = 0에 +1(idx = 0) > 1+2 (idx = 1) > 3+3 (idx = 2) > 6+4 (idx = 3) > target과 result가 같은지 확인 (idx = 4)

idx = 3로 돌아와 - 실행 (6-4 = 2) > target과 result가 같은지 확인 (idx = 4) . . . 이런식으로 진행된다.

 

// bfs : 큐를 이용
// dfs : 시스템 스택 이용

class Solution {
    static int result = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return result;
    }
    
    public static void dfs(int[] numbers, int target, int idx, int cur){
        
        if(idx==numbers.length){
            if(cur==target){
                result++;
            }
            
            return;
        }
        
        for(int d=0;d<2;d++){
            if(d==0) dfs(numbers, target, idx+1, cur+numbers[idx]);
            else dfs(numbers, target, idx+1, cur-numbers[idx]);
        }
    }
}

 

 

 

방법2) BFS

BFS는 Queue를 사용하는 방법이다.

만약 numbers = [1,2,3,4]라면 아래와 같은 갈래길을 볼 수 있을 것이다.

 

0이었던 수가

첫 번째 가지에서는 3, -1, 1, -3과 같은 수가 나올 수 있으며,

두 번째 가지에서는 6, -4, 4, -2, 0, -6과 같은 수가 나올 수 있는 것이다.

 

n+1번째 가지에 있는 수들은 n번째 가지의 +숫자 -숫자를 해줘서 변화한 것이다.

- n번째 가지들의 수 중 하나를 큐에서 꺼내서 +숫자 -숫자 2가지를 해 준 버전을 다시 큐에 넣는 것이다.

 

 

- 잘못된 접근 방식

// bfs : 큐를 이용
// dfs : 시스템 스택 이용
import java.util.*;
class Solution {
    
    static int result = 0;
    
    public int solution(int[] numbers, int target) {
        bfs(numbers, target);
        return result;
    }
    
    public static void bfs(int[] numbers, int target){
        //1. 처음에는 0이라는 수만 있음
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        
        int idx = 0;
        
        while(!q.isEmpty()){
            int curNum = q.poll();
            System.out.println(curNum);
            
            if(curNum == target) result++;
            
            if(idx<numbers.length){
                q.offer(curNum+numbers[idx]);
                q.offer(curNum-numbers[idx++]);
            }
            
        }
        
    }
}

이런식으로 숫자만 큐에 넣어서 관리하면,

 

0 -> -1, 1까지는 괜찮지만

-1 -> 1, -3   (+2 ,-2를 한 것)

1에서는 +3 -3을 하고 만다. 즉, 같은 0에서 가지가 나왔지만, +2 -2는 적용되지 않는 모습이다.

따라서 어떤 level에서 뻗어나온 수인지 함께 저장하고, n 레벨이라면 n+1 인덱스 수를 더하고 빼야하는 것이다.

 

그리고 주의해야 할 점은 모든 수의 부호가 정해졌을 때만 target 수와 같은지 비교한다.

각 depth 별로 일일이 비교하지 않는다. -> 글쓴이는 일일이 비교했더니 무한 루프를 돌았다...

 

(아 못풀겠다...)