[Java] 프로그래머스_43165 : 타겟 넘버

깊이 우선 탐색(DFS)

타겟 넘버 - Level2

 

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

프로그래머스

 

 

 

풀이

import java.util.*;

class Solution {
    
    private static class State {
        public final int idx;
        public final int acc;
        
        State(int idx, int acc) {
            this.idx = idx;
            this.acc = acc;
        }
    }
    
    public int solution(int[] numbers, int target) {
        // 한 번 탐색할 때마다 탐색 공간엥서 서로 다른 경로를 선택하고, 서로 다른 방식으로 도살한 상태는 서로 다른 연산자를 쓰게 되므로 중복이 발생하지 않음 => 방문 검사 필요x
        // 중복 검사 : 중복이 발생하지 않으므로 중복 검사 필요x
        
        // 초기 상태 : 아무런 연산자도 정해지지 않았고, 아무런 값도 누적되지 않았을 경우
        Stack<State> s = new Stack<>();
        s.push(new State(0, 0));
        
        int cnt = 0;
        
        // 탐색 진행 : 전체 탐색 공간의 탐색을 진행
        while (!s.isEmpty()) {
            State state = s.pop();
            // 현재 상태 처리 : 모든 연산자가 정해질 때는 탐색의 최대 깊이에 도달했을 경우이다.
            // 이 경우 타깃 넘버만큼 누적되었는지 검사하여 그 경우의 수를 세야 한다.
            
            if (state.idx == numbers.length) {
                if (state.acc == target) cnt++;
                continue;
            }
            
            // 전이 상태 생성 후 상태 전이
            // -를 선택한 경우
            s.push(new State(state.idx + 1, state.acc - numbers[state.idx]));
            // +를 선택한 경우
            s.push(new State(state.idx + 1, state.acc + numbers[state.idx]));
        }
        return cnt;
    }
}

 

 

[1, 1, 1, 1, 1] 배열과 target이 3인 경우

1. 초기 상태: 스택은 초기 상태 State(0, 0)로 시작한다. 즉, 아직 어떤 숫자도 사용하지 않았고 누적된 합은 0이다.

2. 첫 번째 반복 (state: State(0, 0))
	• -1: 누적된 합에 -1을 더한 다음의 상태 State(1, -1)을 스택에 추가한다.
	• 1: 누적된 합에 1을 더한 다음의 상태 State(1, 1)을 스택에 추가한다.
	스택은 [State(1, -1), State(1, 1)]가 된다.

3. 두 번째 반복 (state: State(1, 1))
    • -1: 누적된 합에 -1을 더한 다음의 상태 State(2, 0)을 스택에 추가한다.
    • 1: 누적된 합에 1을 더한 다음의 상태 State(2, 2)을 스택에 추가한다.
	스택은 [State(2, 0), State(2, 2)]가 된다.

4. 세 번째 반복 (state: State(2, 2))
    • -1: 누적된 합에 -1을 더한 다음의 상태 State(3, 1)을 스택에 추가한다.
    • 1: 누적된 합에 1을 더한 다음의 상태 State(3, 3)을 스택에 추가한다.
	스택은 [State(3, 1), State(3, 3)]가 된다.

5. 네 번째 반복 (state: State(3, 3))
    • -1: 누적된 합에 -1을 더한 다음의 상태 State(4, 2)을 스택에 추가한다.
    • 1: 누적된 합에 1을 더한 다음의 상태 State(4, 4)을 스택에 추가한다.
	스택은 [State(4, 2), State(4, 4)]가 된다.

6. 다섯 번째 반복 (state: State(4, 4))
	• -1: 누적된 합에 -1을 더한 다음의 상태 State(5, 3)을 스택에 추가한다.
	• 1: 누적된 합에 1을 더한 다음의 상태 State(5, 5)을 스택에 추가한다.
	스택은 [State(5, 3), State(5, 5)]가 된다.

7. 여섯 번째 반복 (state: State(5, 5))
	• 이 시점에서 state.idx가 numbers.length (5)와 같으며, 누적된 합이 5이다. 
    누적된 합이 목표 값과 같으므로 카운트(cnt)를 1 증가시킨다.
	스택은 이제 비어 있다.

최종 결과: 카운트 cnt는 5로, 주어진 숫자와 덧셈/뺄셈 연산을 사용하여 목표 합계 3을 만들 수 있는 방법의 수입니다.

 

 

 

DFS를 스택으로 구현

// (1) 방문 검사 배열
boolean[] isVisited = new boolean[N];

Stack<Integer> stack = new Stack<>();
// (2) 초기 상태
stack.add(/* initialState= */ 0);

// (3) 탐색 진행
while (!stack.isEmpty()) {
	int state = stack.pop();
    
    // (4) 중복 검사
    if (isVisited[state]) continue;
    isVisted[state] = true;
    
    // (5) 현재 상태 처리
    /* 현재 상태 state 처리 */
    
    // (6) 전이 상태 생성
    for (int next : getNextStates(state)) {
    	// (7) 범위 검사
        if (!/* 범위 검사 조건 */) {
        	// 문제 범위를 벗어나는 상태는 제외한다.
            continue;
        }
        
        // (8) 유효성 검사
        if (!/* 유효성 검사 조건 */) {
        	// 문제의 조건을 어기는 상태는 제외한다.
            continue;
        }
        
        // (9) 상태 전이
        stack.push(next);
    }
}

 

• 방문 검사 배열 초기화 (1): isVisited 배열은 각 상태를 방문했는지 여부를 저장하는 배열이다. 초기에는 모든 상태를 방문하지 않은 상태로 초기화 한다.
• 스택 초기화 (2): stack은 방문할 상태를 저장하는 스택이다.
• 초기 상태 추가 (3): 탐색을 시작할 초기 상태를 스택에 추가한다. 이 코드에서는 0번 상태부터 시작하도록 되어 있습니다.
• 탐색 진행 (3-9): 스택이 비어있지 않은 동안 계속해서 탐색을 진행한다.
• 중복 검사 (4): 이미 방문한 상태인지 검사한다. 이미 방문한 상태라면 더 이상 진행하지 않고 다음 상태로 넘어간다.
• 현재 상태 처리 (5): 현재 상태를 처리한다. 이 부분에는 현재 상태에 대한 작업이 들어간다.
• 전이 상태 생성 및 전이 (6-9): 현재 상태에서 다음 상태로 전이할 수 있는 모든 상태를 생성하고, 그 상태들을 스택에 추가한다. 이때 범위 검사와 유효성 검사를 거쳐야 한다. 범위 검사는 문제에서 주어진 범위 내에서만 상태를 전이하도록 하는 역할을 한다. 유효성 검사는 문제에서 주어진 조건을 만족하는 상태만을 추가하도록 하는 역할을 한다.

 

 

 

 

아직 문제를 분석하는 데 어려움을 겪고 있다. 이는 차츰 나아질 것이라고 생각한다.

그런데 풀이 과정 중에 +를 선택한 경우인데, 왜 state.acc - numbers[state.idx] 를 하는지 이해가 가지 않았다. 그런데 알고 보니 그냥 책의 오타였다. 

// +를 선택한 경우
s.push(new State(state.idx + 1, state.acc - numbers[state.idx]));
// -를 선택한 경우
s.push(new State(state.idx + 1, state.acc + numbers[state.idx]));

 

=> 책에서 위와 같이 써있어서 혼동이 있었다. 그런데 알고보니 그냥 오타였다 ^-^

=> 그냥 아래와 같이 고쳐서 생각하면 됐다...(허무)

// -를 선택한 경우
s.push(new State(state.idx + 1, state.acc - numbers[state.idx]));
// +를 선택한 경우
s.push(new State(state.idx + 1, state.acc + numbers[state.idx]));