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

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

• 문제 이해
• 해결 방법
• 구현

---

문제 이해

 

먼저 N, M 두 숫자를 입력받는다. N은 1부터 N까지를 의미한다.

M은 출력 자릿수를 결정한다.

이 문제 N과 M (1)은 M 자릿수를 출력하며 1부터 N까지 중복 없이 출력하는 경우이다. 이 문제의 출력은 결국 순열을 의미한다.

N과 M 문제 시리즈 같은 경우는 순열, 중복순열, 조합, 중복 조합 등을 백트래킹을 이용해서 구현하는 방법을 훈련할 수 있다.

이 문제는 백트래킹을 몰랐다면 풀기 어려웠을 것 같다.

 

 

---

해결 방법

 

우선 재귀 함수를 이용하여 자리수를 하나씩 채워간다. 즉 재귀가 될 때마다 자릿수가 다음 자릿수로 넘어간다.

재귀의 인자로 자리수 번호를 0부터 시작하여 앞부터 채워나간다.

재귀가 진행될 때 마다 0 1 2 3 4 자릿수를 채워나간다. 자릿수를 넘치면 종료 조건이 된다. 

재귀 함수 내에서 반복문으로 1부터 N까지 진행하게 해 두고 반복 문안에 재귀 함수를 만들어두면 1 -> 1- > 1 ->....로 재귀 함수가 호출이 되고, 자릿수가 넘쳐서 종료 조건을 만나면 이전 재귀함수로 돌아와 1 -> 1 -> 1 -> 2 이런 식으로 다음 반복을 진행하게 되어 모든 경우의 수를 출력할 수 있을 것이다.

하지만 이 방법은 중복순열이 되므로 중복된 숫자를 출력하지 않게 하도록 방문처리를 해주어야 했다.

 

중복된 숫자를 출력하지 않도록 하는 중복처리는 boolean[] 배열을 이용해서 재귀 함수 호출 이전에 for문 안에서

방문하지 않았다면 방문 처리한 후 다음 재귀 함수를 호출해서 다음 재귀로 넘어가도록 하였다.

이렇게 되면 다음 재귀 함수에서 1부터 사용하려 하겠지만 방문처리가 되었다면 다음 숫자의 반복으로 진행이 되므로

중복된 숫자가 출력되지 않도록 처리를 해줄 수 있다.

재귀 함수가 종료조건을 만나면 이전 재귀 함수 위치로 돌아오고 해당 수의 방문처리를 해제해준다.

여기서 이런식으로 방문 처리를 해제해주면 어차피 다음 반복문은 +1 이므로 해당 자릿수에서는 같은 숫자를 출력하지 않을 것이다.

* 예를들어 1234 출력 후 1234가 다시 안 되는 이유는 다음 반복을 진행하므로 1235가 된다. 

결국 방문처리 해제는 해당 자리수를 위한 것이 아니라 반복문이 전부 종료되면 이전 자릿수의 재귀 함수 호출로 돌아갈 것이므로 그곳에서

해당 숫자를 사용하기 위해 해체해주는 것이다.

 

마지막으로 재귀가 진행될때마다 자릿수에 중복 없이 저장될 숫자를 저장할 배열을 자리수 크기만큼 만들어둔다.

재귀 함수의 종료 조건은 자릿수가 넘치면 종료된다.

배열은 index가 0부터 시작하므로 자릿수가 넘치는 경우는 각 숫자를 저장한 배열의 index가 M 자릿수가 될 때이다.

재귀 함수를 종료시키며 이때 숫자를 저장해두었던 배열을 출력한다.

 

 

---

구현

 

import java.io.*;
import java.util.*;
 
public class BackTracking_boj15649{
    static boolean[] used = new boolean[10]; 
    static int[] arr = new int[10]; 
    static int N;
    static int M;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        N = Integer.parseInt(st.nextToken()); 
        M = Integer.parseInt(st.nextToken());
        BT(0); 
    }
    public static void BT(int k){ // 현재 자리수
        if(M == k){  // 자리수가 넘치면 종료
            for(int j=0; j<10; j++)
                System.out.print(arr[j]+ " ");
            System.out.println();
            return;
        }
        
       
        for(int i =1; i<=N; i++){ // 자리수 마다 반복
            if(!used[i]){
                used[i] = true; // 사용 숫자 방문 처리
 
                arr[k] = i; // 배열에 해당 자리수 숫자 입력
                BT(k+1);
 
                used[i] = false; // 사용 숫자 방문 해제
            }
        }
    }
}