JAVA [Algorithm] - 백준 15650 N과 M (2)

 

📝문제 설명

 

---

📢입출력 예시

 

---

✏️문제 풀이

이 문제 또한 예제 2번의 출력을 보며 규칙을 이해해보자.

(1,2)와 (2,1)은 같은 경우로 취급하여 출력을 안한다.

똑같이 (2,4)은 (4,2)와 같은 경우로 취급하여 출력을 안한다.

 

이제 그림으로 이해해보자

 

그림을 잘 보면 depth 0일 때의 재귀함수에서 depth 1로 넘어갈 때

십의자리수의 값에서 +1 한만큼 일의자리수에 넣어주는 것을 볼 수 있다.

 

이러면 다음 재귀함수로 넘어갈 때 십의 자리수에 채워진 어떤 변수 값을 depth 1로 +1만큼 더하고 가져가야 한다.

 

package Baekjoon.BackTracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baek15650 {

    static int[] map;
    static boolean[] visited;
    static int N, M;
    static StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());

        map = new int[M];
        visited = new boolean[N];

        backTracking(0,0);
        System.out.println(stringBuilder);
    }

    public static void backTracking(int num, int depth){
        if(depth == M){
            for(int n : map){
                stringBuilder.append(n).append(' ');
            }
            stringBuilder.append('\n');
            return;
        }

        for(int i=num; i<N; i++){
            if(!visited[i]){
                map[depth] = i+1;
                visited[i] = true;
                backTracking(i+1, depth+1);
                visited[i] = false;
            }
        }
    }
}

 

 

---

💡새로 알게된 점

이게 텍스트로 설명하려니깐 많이 부족하네요...

---