📌 문제

[15649] N과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

⬇️ 입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

⬆️ 출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

💡 코드

✅ 이번 단계는 백트래킹 단계인데, 백트래킹이란 가능한 모든 경로를 탐색하다가, 조건에 맞지 않는 값이 발생하면 더이상 나가지 않고 이전 노드로 다시 돌아가는 알고리즘이다. 이러한 과정을 가지치기라고 한다!

백트래킹이라는 알고리즘을 처음 접해봐서 구글링의 도움을 빌려 해결했다. 코드랑 설명을 아무리 봐도 도저히 이해가 안돼서 결국 재귀를 직접 손으로 써보는,, 지경에 이르렀고,, 결국 이 방법으로 이해에 성공했다! ㅎㅎ

기본적으로 isUsed[]는 출력에 해당 숫자를 사용했는지 판단하는 boolean 타입 배열이고, arr[]는 출력할 m개의 수를 저장하는 int 타입 배열이다. 메서드 dfs(idx)는 배열 arr[]의 인덱스 idx를 전달받아 해당 인덱스에 가능한 값을 저장하고, 재귀 함수를 호출하여 다음 인덱스, ..., m-1번 인덱스 에 저장할 값을 찾는 메서드이다.

static void dfs(int idx) {
		
		if(idx == 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]) {
				isUsed[i] = true;    
				arr[idx] = i;
				dfs(idx+1);
				isUsed[i] = false;
			}
		}
	}

1. dfs(0) : 을 호출하여 idx 값으로 0을 넘겨주면 for문을 통해 arr[idx]에 1을 저장하고, isUsed[1] = true로 변경한 후 다음 인덱스인 dfs(1)를 호출한다.

2. dfs(1) : isUsed[1] = true 이므로 i = 1은 건너뛰고, i = 2일 때 isUsed[2] = true ➡️ arr[1] = 2 ➡️ dfs(2) 호출

3. dfs(2) : i = 3일 때 isUsed[3] = true ➡️ arr[2] = 3 ➡️ dfs(3) 호출

4. dfs(3) : idx = 3 = m 이므로 배열 내의 요소 1 2 3을 출력하고 종료 ➡️ 이전 단계인 dfs(2)로 돌아가 isUsed[3] = false

5. dfs(2) : i = 4일 때 isUsed[4] = true ➡️ arr[2] = 4 ➡️ dfs(4) 호출

6. dfs(3) : 4번 과정과 동일

7. dfs(2) : for문을 조건만큼 모두 돌았으므로 종료 ➡️ 이전 단계인 dfs(1)로 돌아가 isUsed[2] = false

8. dfs(1) : i = 3일 때 isUsed[3] = true ➡️ arr[1] = 3 ➡️ dfs(2) 호출

...

대충 이런식으로 하나씩 써가면서 흐름을 잡다보니 이해가 됐다!

import java.io.*;
import java.util.*;
public class Main {
	
	static int n, m;
	static boolean[] isUsed;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();
	
	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());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		isUsed = new boolean[n+1];
		arr = new int[m+1];
		
		dfs(0);
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
	
	static void dfs(int idx) {
		
		if(idx == 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]) {
				isUsed[i] = true;    
				arr[idx] = i;
				dfs(idx+1);
				isUsed[i] = false;
			}
		}
	}
}