https://www.acmicpc.net/problem/15649
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
풀이과정
해당 문제는 백준의 백트래킹 카테고리의 첫 번째 문제이다.
백트래킹을 모르는 내 입장에선 문제의 입력 범위가 1에서 8이므로 8중 반복문을 사용하면 풀 수는 있을 것 같다고 생각했다. 그렇지만 재귀를 사용한 좋은 풀이방법이 있는 듯 했다.
아직 재귀에 1도 익숙해지지못한 나로써는 마땅한 방법을 떠올리기 힘들었다..
결국 방법이 도출되지 않아 백준의 질문 게시판과 구글링을 통해 다른 정답자분들의 풀이 전략을 확인하였다.
먼저 다음 코드는 다른 분들의 답을 참고하여 제출한 코드이다.
public class Main {
static int M;
static int N;
static int[] arr = new int[10];
static boolean[] isUsed = new boolean[10];
static StringBuilder sb = new StringBuilder();
public static void solve( int index ){
if( index == M ){
for( int i = 0; i < M; i++ ){
sb.append(arr[i]).append(" ");
}
sb.append("\n");
return;
}
for( int i = 1; i <= N; i++ ){
if( !isUsed[i] ){
arr[index] = i;
isUsed[i] = true;
solve(index+1);
isUsed[i] = false;
}
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
solve( 0 );
System.out.println(sb);
}
}주요 전략은 이러했다.
재귀에서 가장 중요한 종료 조건은, 현재 숫자를 선택해서 배열에 저장할 때 사용할 index가 M과 같다면 종료. 만약, M이 3이고 현재 선택해야할 index 또한 3이라면 종료이다.
한번 선택했던 숫자(중복 숫자)는 boolean 배열을 통해 확인한다. 만약 boolean 배열에 해당 숫자가 true로 저장되어 있다면 해당 탐색은 중단한다.
N = 3, M = 2라고 가정해보자.
그리고 길이 3인 빈 배열이 있다. 나는 숫자 1, 2, 3으로 길이 2인 모든 조합을 맞춰야한다.
재귀적으로 함수를 호출해 들어갈 때마다 현재 숫자를 채워넣을 공간을 뜻하는 index는 1씩 증가한다.
위의 코드와 비교하여 보면 index가 0일 때 0번째 배열에 1을 넣었고, index가 1일 때 두 갈래로 나누어져 2와 3을 넣은 것을 볼 수 있다.
모든 흐름을 살펴보면 아래 이미지와 같다.
나가는 글
재귀 카테고리로 넘어오면서부터 방법을 전혀 못떠올리는 일이 잦아졌다. 여러 문제를 경험해보며 스킬을 익히는 것만이 정답인 것 같다. 모든 알고리즘 기술들의 숙련을 소망하며 더 열심히 학습해보자.
