Java 백준 문제풀이 (35) 15651: N과 M (3)

 

중복 순열을 백트래킹으로 구하는 문제다.

2주 전에 접했을 때는 너무 어렵게 느껴졌었는데, 그래프를 먼저 배우고 와서 다시 보니 어처구니 없을 정도로 쉬운 문제였다.

대체 왜 단계별 알고리즘에 백트래킹을 그래프보다 앞에 둔 건가요 백준..

 

백트래킹은 기본적으로 DFS 알고리즘을 조금 보완한 거라서 DFS 알고리즘을 먼저 배우고 와야한다.

DFS 배우고 오면 진짜 별거 없음..

 

 

 

이게 중복 순열을 구하는 알고리즘을 한 컷에 요약한 그림이다.

(A,A,A) (A,A,B) (A,A,C) (A,B,A) (A,B,B) (A,B,C)..

 

백트래킹 알고리즘의 기본 뼈대는 이런 식이다.

 

void 응애_백트래킹(int num) {

 if ( 만약에 조건에 부합한다면 )

 { 값을 리턴해줘 }

 if ( 이 노드가 내가 찾는 값이랑 무관하다면 )

 { 시간 낭비하지 말고 그만 탐색해 }

 

for (반복문) { 

재귀()

}

}

 

근데 중복 순열은 조건에 부합하는 노드는 모두 가져오면 되기 때문에 조건(깊이)만 설정해서 죄다 뽑아내면 된다.

깊이라는 말에 거부감을 느낄 이유가 없다. 위 그림에서 "A","B","C"로 3글자를 이어 붙일 수 있는 경우의 수를 구하라고 하면 depth 3까지 구하라는 말과 동일하다.

 

백트래킹은 그림을 보면서 생각해야 이해하기 쉽다. AA ~ 인 경우를 모두 구해야하니까 AA에서 재귀 AB ~인 경우도 모두 구해야하니까 AB에서 재귀 AC~ 인경우를 모두 구해야하니까 AC에서 재귀.

무슨 헛소리인가 싶을 수도 있지만 정말 이게 전부다.

처음 보면 어려운 게 당연한데 생각보다 별 거 없으니 좌절하지 말자.

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static final int MIN_VALUE = 1; // 문제에서 제시한 최소값
    static StringBuilder sb = new StringBuilder();
    static int numRange = 0; // 숫자 범위
    static int numberPick = 0; // 뽑을 숫자 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        numRange = Integer.parseInt(st.nextToken());
        numberPick = Integer.parseInt(st.nextToken());
        ArrayList<Integer> temp = new ArrayList<>(); // 수열을 담을 배열
 
        backTracking(1, temp); // 백트래킹 메서드
        System.out.println(sb.toString());
    }
 
    public static void backTracking(int num, ArrayList<Integer> temp) {
        if ( temp.size() == numberPick ) { // 배열에 뽑으려는 숫자 개수만큼 값이 들어가면
            for ( int n : temp ) {
                sb.append(n).append(" "); // 스트링 빌더에 값을 넣어주삼
            }
            sb.append("\n");
            return;
        }
 
        for (int i=MIN_VALUE; i<=numRange; i++) {
            temp.add(i); // 0부터 범위까지 값을 넣는다
            backTracking(i,temp); // 만약 트리 끝까지 내려갔다면 리턴되겠죠
            temp.remove(temp.size()-1); 
        }
    }
}