백트래킹 - 백준15650 N과 M(2)

이전 문제 N과 M(1) 문제에 이어 N과 M(2) 문제이다.
이 N과 M 문제 시리즈를 다 풀어 볼 작정인데 굳이 다 올려야하나 싶은 생각이 들었지만, 일단 이 문제 같은 경우는 쓰고 싶어서 한 번 써본다.

문제 설명
이전 N과 M(1) 문제와 문제 지문은 똑같다. 하지만 출력 결과를 보면 차이가 있다.
이전 문제는 1~N 중 m개의 조합인 경우의 수를 모두 출력한다.
본 문제는 위 결과의 조합들 중 원소가 같은 조합들은 첫 번째로 나온 하나만 출력한다.

여기서 참고해야 할 중요한 사실은 위 설명은 문제를 필자가 해석한대로 설명했다는 것이다. 필자가 서술한 설명이 틀린 것은 아니다. 하지만 문제를 어떻게 해석하느냐에 따라 이를 구현하는 풀이가 완전히 달라진다.

풀이 시도
위 해석에 따라 N과 M(1) 문제의 풀이에서 어떻게 원소가 같은 조합들을 제거하는 로직을 추가할 수 있을지 고민했다. 사용중인 숫자를 체크하는 boolean배열을 하나 더 만들려고 생각해봤지만 어떻게 적용해야 할 지 도저히 모르겠었다. 그 외에 다른 방법도 고민해봤지만 생각이 나지 않아 결국 다른 사람들의 풀이를 찾아봤다.

해답
모든 조합을 순서대로 출력하므로, 한 조합에서 뒤의 숫자는 앞의 숫자보다 크다.
ex) 4 1
1 2 3 4 -> 가능
4 1 2 3 -> 불가능
1 2 4 3 -> 불가능
따라서 다음 숫자를 정하는 재귀함수를 호출할 때 현재 fix된 숫자를 넘겨주고, 호출된 함수는 해당 숫자와 비교하여 보다 작은 숫자는 skip한다. 이를 적용한 코드는 다음과 같다.

import java.io.*;
import java.util.*;
public class Main{
	static int n;
    static int m;
    static boolean[] isUsed;
    static int[] answer;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        isUsed = new boolean[n];
        for(int i = 0; i < n; i++){
            isUsed[i] = false;
        }
        answer = new int[m];
        go(0, 0);
    }
    static void go(int now, int before){	//이전 숫자를 함께 넘겨 받음
        if(now == m){
            for(int i = 0; i < m; i++){
                System.out.print(answer[i] + " ");
            }
            System.out.println();
            return;
        }
        for(int i = 1; i <= n; i++){
            if(isUsed[i-1] || i < before){	//이전 숫자보다 작은지 비교
                continue;
            }
            answer[now] = i;
            isUsed[i-1] = true;
            go(now+1, i);
            isUsed[i-1] = false;
            isUsed2[i-1] = true;
        }
    }
}

깨달은 교훈

따라서 이 문제는 처음 설명한 것과 같이 원소가 같은 조합들은 한 번만 출력된다고 해석할 수도 있고, 풀이와 같이 뒤의 숫자는 앞의 숫자보다 클 수 없다라고 해석할 수도 있다. 즉, 문제를 해석하기에 따라 풀이가 달라질 수 있다는 사실을 기억해야 한다. (그래서 백준사이트에도 일부러 다른 설명을 굳이 추가하지 않았나라고 생각된다.)

이 사실을 깨닫게 되어 이 글을 작성하기로 마음먹게 되었다.