JAVA [Algorithm] - 백준 15649 N과 M (1)

 

📝문제 설명

 

---

📢입출력 예시

 

---

✏️문제 풀이

예제 2번을 보면서 고민을 해보자.

예제 2번의 출력의 경우의 수는 아래 그림과 같다.

 

 

규칙을 보면 십의자리수에 있는 숫자는 일의자리수에 올 수 없다는 것을 알 수 있다.

백트래킹 문제는 재귀함수로 풀어지기 때문에 visited 배열을 사용하여 십의 자리숫자에 있는 자리를 true로 처리하여 방문하지 못하게 막아 놓으면 될 것 같다.

 

depth 값을 추가하여 배열의 인덱스 네비게이션 역할을 할 것이다.

십의 자리수가 채워지는 재귀함수에는 depth를 0,

일의 자리수가 채워지는 재귀함수는 depth를 1로 하여 값을 채워보자.

 

package Baekjoon.BackTracking;

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

public class Baek15649 {

    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);
        System.out.println(stringBuilder);
    }

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

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

 

---

💡새로 알게된 점

 

규칙은 알겠지만 코드화 해보려니 머리가 터질 것 같아 대학교 전공 수업 때 배운 재귀함수 풀이법(?)을 사용해서 코드화를 해보니 그나마 이해가 간다  

---