[백준 #15649] N과 M (1)

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

 

문제

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

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

 

입력

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

 

출력

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

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

예제	입력	출력
1	3 1	1 2 3
2	4 2	1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3
3	4 4	1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1

 

해결 코드

import java.util.Scanner;
public class Main {
	// n과 m
	// 중복없이 m개 숫자를 1부터 n 사이 수 선택
	
	//1. 재귀로 DFS 방식 구현 가능
	
	static boolean usedAlready[];
	static int current[];
	static int m;
	static int n;
	
	static StringBuffer sb = new StringBuffer();
	
	public static void nextNumber(int current_m) {
		
		if(current_m == 0) {
			for(int i=0; i<m; i++) sb.append(current[i] + " ");
			sb.append("\n");
			return;
		}
		
		for(int i=1; i<=n; i++) {
			if(usedAlready[i] == true) continue;
			usedAlready[i] = true;
			current[m - current_m] = i;
			nextNumber(current_m - 1);
			usedAlready[i] = false;
		}
		
	}
	
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		m = scanner.nextInt();
		
		usedAlready = new boolean[n+1];
		current = new int[m];
		
		for(int i=1; i<=n; i++) {
			usedAlready[i] = true;
			current[0] = i;
			nextNumber(m-1);
			usedAlready[i] = false;
		}
		
		System.out.println(sb);
		
	}
	
}

 

이 문제는 백트래킹(Backtracking) 기법을 사용하여 1부터  n 까지의 숫자 중에서 중복 없이  m 개의 숫자를 선택하는 모든 경우의 수를 구하는 알고리즘을 구현하면 해결할 수 있다.

 

 

 

---

1. 자료구조 분석

 

1) usedAlready (사용 여부 체크)

static boolean usedAlready[];

 

• 역할: 특정 숫자를 사용했는지 여부를 기록하는 불리언 배열

• 크기: n+1 (1번 인덱스부터 사용)

• 활용: 숫자가 한 번 선택되면 true로 설정하여 다시 선택되지 않도록 함

 

---

 

2) current (현재 선택한 숫자 저장)

static int current[];

 

• 역할: 현재까지 선택한 숫자들을 저장하는 정수 배열

• 크기: m (선택할 숫자의 개수)

• 활용: 깊이 우선 탐색(DFS) 진행 중 현재까지 선택한 숫자들을 저장하는 용도

 

---

 

3) sb (출력 최적화)

static StringBuffer sb = new StringBuffer();

 

• 역할: System.out.println() 대신 StringBuffer를 사용하여 출력 성능을 향상

• 이유: System.out.println()을 여러 번 호출하면 속도가 느려지므로 한 번에 문자열을 만들고 출력하는 방식 사용

 

 

 

---

2. 알고리즘 분석

이 코드는 재귀를 이용한 DFS(깊이 우선 탐색, Depth First Search) 알고리즘을 사용하여 모든 가능한 조합을 생성한다.

 

1) 재귀 함수 (nextNumber)

public static void nextNumber(int current_m) {

 

• 매개변수: current_m (현재 선택해야 하는 남은 숫자의 개수)

• 종료 조건: current_m == 0이면 현재까지 선택한 숫자를 출력하고 종료

• 재귀 호출: 사용하지 않은 숫자를 선택하여 깊이 탐색

 

2) 백트래킹 로직

for(int i=1; i<=n; i++) {
	if(usedAlready[i] == true) continue;
	usedAlready[i] = true;
	current[m - current_m] = i;
	nextNumber(current_m - 1);
	usedAlready[i] = false;
}

 

• usedAlready[i] == true이면 이미 사용된 숫자이므로 건너뜀

• usedAlready[i] = true;로 설정하여 중복을 방지한 후 재귀 호출

• 탐색이 끝나면 usedAlready[i] = false;로 원래 상태로 되돌려 백트래킹 수행

 

 

 

---

3. 시간 복잡도 분석

• n개의 숫자 중에서 m개를 선택하는 순열 문제이므로 O(nPm) (n P m = n! / (n-m)!)

• n이 8 이하이므로 최악의 경우  O(8P8 = 8!) = 40,320 로 충분히 수행 가능

 

 

 

---

4. 최적화 요소

 

System.out.println() 대신 StringBuffer 사용

• 여러 개의 결과를 한 번에 출력하여 성능 최적화

백트래킹을 활용하여 불필요한 탐색 줄임

• 선택된 숫자를 되돌리는 방식(usedAlready[i] = false;)으로 상태 복구

 

 

 

---

5. 결론

백트래킹(Backtracking) 기법을 사용하여 중복 없이 숫자를 선택하는 모든 경우의 수를 생성하는 DFS 기반 알고리즘을 구현하는 문제였다. 이때, usedAlready를 활용하여 중복을 방지하며, StringBuffer를 이용해 출력 속도를 최적화했다.