BOJ 15649 N과 M (1) [Java]

BOJ 15649 N과 M (1)

1. 문제 링크

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

2. 문제 해설

백트래킹을 할 때는 문제에서 주어진 조건을 잘 살펴야한다. 이 문제에서는 중복 없이 숫자 선택, 사전 순으로 수열 출력 이 2가지 조건만 만족하면 된다.
중복 체크를 하기 위해 vis 배열을 만들어주고, m개의 선택된 숫자를 담을 arr 배열을 만들어준다.
이제 백트래킹 과정을 행할 solve 메서드에 대해 알아보자.
매개 변수로 cnt를 받는데 cnt가 의미하는 바는 선택된 숫자의 갯수이다.
탈출 조건은 cnt가 의미하는 바를 생각하면 자연스레 도출된다. cnt == m 이 되면 solve 메서드를 탈출하고 arr 배열에 저장된 숫자들을 StringBuilder에 담는다.
이제 solve 메서드의 메인 로직에 대해 알아보자.
n번의 루프를 도는데, 중복을 허용하지 않으므로 만약 이미 선택한 숫자이면 넘어간다.
선택하지 않았다면, arr 배열에 담아준다. 이때 배열에서 담기는 위치의 인덱스는 cnt와 같다. 그 후, 선택했다고 표시해준다.
한 개의 숫자를 선택했으므로 다음 숫자를 선택하기 위해 solve 메서드를 재귀적으로 호출해준다.
재귀적으로 호출된 solve 메서드가 종료되면 현재 숫자에서 나올 수 있는 다음 숫자들의 경우의 수를 모두 돌아봤다는 의미이다.
그러므로 현재 숫자를 다시 선택하지 않은 상태로 만들어준다.

백트래킹을 처음 보면 이해가 잘 되지 않는다. 최대한 절차지향적인 생각을 버리고 재귀적으로 생각하도록 노력해야한다.
정 이해가 되지 않으면 한단계씩 백트래킹 과정을 손으로 진행해보는 것도 괜찮다.

3. 코드 보기

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb;
    static int n, m;
    static int[] arr;
    static boolean[] vis;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        vis = new boolean[n];

        solve(0);

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }

    static void solve(int cnt) {
        if (cnt == m) {
            for (int i = 0; i < m; i++) {
                sb.append(arr[i]).append(' ');
            }

            sb.append('\n');
            return;
        }

        for (int i = 0; i < n; i++) {
            if (vis[i]) {
                continue;
            }

            arr[cnt] = i + 1;
            vis[i] = true;
            solve(cnt + 1);
            vis[i] = false;
        }
    }
}