백준 15653 N과 M (5) (JAVA 자바 풀이)
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
- N개의 자연수 중에서 M개를 고른 수열
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
💡 풀이 과정
먼저 문제의 요건을 정리해보면 다음과 같다.
- N개의 자연수 집합에서 M개를 고른 수열 : 1 <=M <= N <= 8, 원소 <= 10000
- 수열은 사전 순으로 출력
- 중복되는 수열을 여러 번 출력하면 안 됨 (N개는 모두 다른 자연수)
먼저 모든 경우를 탐색한다면 시간 복잡도가 어떻게 될까?
N과 M이 최대값인 8에서, 최대 케이스를 계산해보면 8개의 숫자 안에서 8개를 숫자를 뽑아서 나열하게 될 것이고
순열 공식인 8! 계산 값이 나온다.
이는 약 40,000번의 연산을 의미하므로 brute force로도 풀이가 가능할 것으로 추정된다.
그렇다면 어떻게 구현할 수 있을까?
먼저 문제의 요건에 따라 사전 순 출력을 위해 먼저 값을 정렬해주자.
입력을 받고 정렬하기까지 코드는 다음과 같다.
int[] numbers = new int[N];
stringTokenizer = receiveInput(bufferedReader);
for (int i = 0; i < N; i++) {
numbers[i] = parseInt(stringTokenizer.nextToken());
}
sort(numbers); // 주어진 수열 정렬
그 다음 하나씩 뽑는 경우를 생각해 보자. 1 2 3 4 5라는 숫자가 있을 때 3개를 뽑아야 한다면
1 2 3, 1 2 4, 1 2 5, 1 3 2, 1 3 4, 1 3 5, 1 4 2, ... 이런식으로 뽑히게 될 것이다.
이를 배열을 통해 구현한다고 하면
[0] [1] [2] [3] [4] 배열에 값이 저장되어 있다고 할 때
먼저 [0]을 뽑고 -> 1
그 다음 [1] 을 뽑고 -> 2
그 다음 [2] 를 뽑을 것이다 -> 3
그렇다면 이제 다음 스텝으로 어떻게 3을 빼고 4를 뽑을 수 있을까?
이를 백트래킹 알고리즘으로 구현할 수 있다. 백트래킹은 해결책에 대한 후보를 구축해 나가다가, 해당 후보가 해결책이 될 수 없다고 판단되는 즉시 이 후보를 포기(Backtrack)하는 방식이다.
1 2 3 을 뽑은 상황을 생각해보자. 이미 요구하는 3자리 숫자를 다 뽑은 상황인 것이다. 그렇다면 이를 depth 변수로 두고, 하나씩 숫자를 뽑을 때마다 해당 값을 올려주면 어떨까? 3자리 수가 되는 순간이면 종료시키고 값을 출력한다.
즉, depth가 M과 같을 때 해당 숫자를 출력한다.
if (depth == M) {
// M개를 모두 선택했을 때 결과를 출력
for (int i = 0; i < M; i++) {
System.out.print(selected[i] + " ");
}
System.out.println();
return;
}
위의 코드에서 보면 반복문을 돌면서 출력하는 부분은 저장해둔 숫자를 출력하는 내용이다. 예를 들어, 1 2 3을 뽑았으면 그 숫자들을 저장해 놓았어야 하는 것이고, 이를 출력하는 부분이다.
그럼 다음 진행은 어떻게 할까?
아직 M개의 숫자를 선택하지 않았을 때를 생각 해보자. 중복을 허용하지 않는다고 했으므로 남은 숫자들 중 하나를 선택하고, depth를 1 증가시킬 것이다.
for (int i = 0; i < N; i++) {
// 아직 선택하지 않은 숫자 선택
selected[depth] = numbers[i];
}
그런데 이 반복문을 돌면서 선택은 계속 이뤄져야 한다. 여기서 재귀적인 개념으로 자기 자신의 로직을 호출한다. 단, 이때 depth를 한 번 더 올려서 호출하는 것이다.
// 다음 숫자 선택을 위해 백트래킹 함수 재귀 호출
backtrack(depth + 1, N, M, numbers, selected);
그런데 이 로직에서 중복 허용 체크하는 부분이 없으므로 호출 전에 중복을 체크하고 중복되지 않은 값들만 호출해주자. 즉, 다음과 같은 코드를 선행 조건으로 추가한다.
if (!used[i]) {
used[i] = true; // 숫자 사용 표시
백트래킹이 끝나면 다음 항목에서 사용되어야 하므로 중복 체크를 풀어준다.
used[i] = false; // 숫자 사용 해제
이를 전체 코드로 구현해 보면 다음과 같다. 재귀함수 호출에서 사용되는 numbers, N, M은 모두 고정된 숫자이므로 static 변수로 올려주고, selected와 used 역시 매번 달라지기는 하지만 공통적으로 계속 사용되니 static으로 바꿔 사용하자.
그렇게 되면 함수 호출시마다 바뀌어야 하는 변수는 depth 하나만 이므로 보다 코드가 간단해진다.
💡 코드 구현
import static java.lang.Integer.*;
import static java.util.Arrays.*;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
private static boolean used[]; // 숫자의 사용 여부를 저장하는 배열
private static int selected[]; // 선택된 숫자를 저장하는 배열
private static int numbers[]; // 입력받은 숫자들을 저장하는 배열
private static int N; // 전체 숫자의 개수
private static int M; // 선택할 숫자의 개수
private static StringTokenizer receiveInput(BufferedReader bufferedReader) throws IOException {
return new StringTokenizer(bufferedReader.readLine());
}
public static void main(String[] args) throws IOException {
// BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));
StringTokenizer stringTokenizer = receiveInput(bufferedReader);
N = parseInt(stringTokenizer.nextToken());
M = parseInt(stringTokenizer.nextToken());
numbers = new int[N];
stringTokenizer = receiveInput(bufferedReader);
for (int i = 0; i < N; i++) {
numbers[i] = parseInt(stringTokenizer.nextToken());
}
sort(numbers); // 주어진 수열 정렬
used = new boolean[N];
selected = new int[M];
permutation(0); // 순열 생성 함수 호출
}
private static void permutation(int depth){
if (depth == M) {
// M개를 모두 선택했을 때 결과를 출력
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < M; i++) {
stringBuilder.append(selected[i]).append(" ");
}
System.out.println(stringBuilder);
return;
}
for (int i =0; i< N; i++){
if(!used[i]){ // 중복 되지 않았을 때에만 알고리즘 진행 -> 즉, 선택
used[i] = true;
selected[depth] = numbers[i]; // 현재 깊이(=자리수)에 해당 숫자를 선택
permutation(depth+1);
used[i] = false;
}
}
}
}
💡 작동 프로세스
위에서 예시로 든 다섯개 숫자 1 2 3 4 5 중 3개를 선택하는 케이스가 코드에서 어떻게 선택되는지 살펴보자.
먼저 처음 1이 선택될 것이다.
이때 depth는 0이고 선택된 것도 없으므로 used[0]도 false이므로 ->
selected[depth] = numbers[i];
코드에 따라 selected[0]에 1이 들어간다.
그 다음 다시 함수가 호출이 되는데 이때는 자리수가 하나 생겼으므로 depth가 하나 증가하여 1이 된다.
이때도 depth는 M과 같지 않고 used[1]도 false이므로 selected[1]에 2가 들어간다. 그런데 이때 왜 0이 한 번 더 들어가지 않을까? used[0]이 true로 방금 체크 되었기 때문이다.
이렇게 해서 selected에 이제 [1, 2, _]가 들어간 상황이고 depth는 한 번 더 올라서 2가 된다. 함수가 다시 호출 되면
여전히 depth 와 M은 같지 않으므로 재귀의 종료 조건인 base 조건에 해당되지는 않지만 벌써 used에 0, 1 이 사용되고 있으므로 이제 그 다음 자리인 2가 선택될 것이다.
그런 다음 재귀가 호출 되고 이때 depth는 3이 된다.
그러면 depth == M 조건이 만족되므로 출력하고 리턴해야 하는 시점이다.
위의 조건에 따라서 출력이 모두 되고 나면 이제 이전에 호출되었던 그 자리로 다시 돌아가서 그 다음 라인의 코드가 호출될 것이다.
즉, 가장 최근 i인 i가 2일때 재귀 호출이 발생한 그 다음,
used[i] = false가 호출되고, 이에 따라 used의 값은 다음과 같이 바뀌고 다음 진행에서 반복문의 조건에 따라 i++ -> i는 3이 된다.
현재 콘솔에는 1 2 3이 출력되어 있다. 그렇다면 이제 1 2 4가 출력되어야 하는데 그렇게 되는지 살펴보자.
i가 3일 때 used는 false이므로 정상 진행이 될 것이고 사용이 체크 되면서 4가 선택된다.
그 뒤 다시 재귀함수가 호출이 되는데 이때 depth는 어떨까?
여전히 2이다. 왜냐하면 이전에 3이 호출된적이 있었는데 ('3' 이 선택될 때) 그때 depth == M 조건에 따라서 출력이 되고 함수가 끝났기 때문이다.
따라서 현재 depth 2인 현재 상황에서 4가 선택된 것이고, 그렇게 해서 depth +1로 3이 되어 다시 호출된 함수는 다시 기저 조건을 만나는데, 이때 또 출력이 발생한다.
이때 선택된 값을 보면 이전의 3이 4로 대체된 것을 볼 수 있다.
동일한 방식으로 1 2 5가 출력될 것이다. 따라서 1 2 3, 1 2 4, 1 2 5가 출력되었다고 치면, 이제 1 3 2가 호출되어야 하는 상황을 살펴보자.
5까지 출력이 되었다면 i가 4까지 올라가서 반복문이 한 번 돌았다는 뜻이다.
이제 함수가 다시 리턴이 되면서 사용하고 있던 1 2 중 2까지 반환을 할 것이고 used 배열은 다음과 같이 바뀐다.
함수가 반환되고 나면, depth는 1로 감소하고, 이제 1이 선택된 상태에서 다음 숫자를 선택해야 한다. used 배열에서 사용 가능한 다음 숫자는 3이다.
즉, i가 0, 1 인 상태에서 depth가 2, 3을 왔다갔다 하면서 1 2 (3-5)를 선택했다면 이제는 1인 상태에서 i가 올라가므로 3이 선택되고 1 3이 선택된 상태에서 2, 4, 5를 depth 3에서 선택하게 된다.
used[2]를 true로 설정하고 selected[1]에 3을 저장한다. 그리고 depth를 증가시켜 재귀 호출을 한다. 이렇게 하면 순열이 [1, 3, _]의 상태가 된다.
이렇게 하여 앞에서의 과정을 반복하면서 중복되지 않은 경우의 수에 따라 숫자를 선택해서 출력한다.
depth과 반복문이 진행되는 흐름을 살펴보자.
초기 상태
- depth = 0
- 선택 배열: []
- 중복 체크 배열: [false, false, false, false, false]
첫 번째 단계: depth = 0
- i = 0
- 선택 배열: [1]
- 중복 체크 배열: [true, false, false, false, false]
- depth = 1로 이동
두 번째 단계: depth = 1
- i = 1
- 선택 배열: [1, 2]
- 중복 체크 배열: [true, true, false, false, false]
- depth = 2로 이동
세 번째 단계: depth = 2
- i = 2
- 선택 배열: [1, 2, 3]
- 중복 체크 배열: [true, true, true, false, false]
- depth = 3 (M=3일 때 여기서 출력하고 리턴)
- 출력: 1 2 3
- used[2] = false로 되돌림
다시 세 번째 단계로 복귀: depth = 2
- i = 3
- 선택 배열: [1, 2, 4]
- 중복 체크 배열: [true, true, false, true, false]
- 출력: 1 2 4
- used[3] = false로 되돌림
다시 세 번째 단계로 복귀: depth = 2
- i = 4
- 선택 배열: [1, 2, 5]
- 중복 체크 배열: [true, true, false, false, true]
- 출력: 1 2 5
- used[4] = false로 되돌림
두 번째 단계로 복귀: depth = 1
- i의 값이 증가함 (i = 2)
- 선택 배열: [1, 3]
- 중복 체크 배열: `[true, false, true, false, false]`
- depth = `로 이동
세 번째 단계: depth = 2
- i = 0
- 이전 단계에서 이미 used[0] = true로 설정됨, 따라서 건너뛰고 i의 값 증가
- i = 1
- 선택 배열: [1, 3, 2]
- 중복 체크 배열: [true, true, true, false, false]
- 출력: 1 3 2
- used[1] = false로 되돌림
- i = 3
- 선택 배열: [1, 3, 4]
- 중복 체크 배열: [true, false, true, true, false]
- 출력: 1 3 4
- used[3] = false로 되돌림
다시 세 번째 단계로 복귀: depth = 2
- i = 4
- 선택 배열: [1, 3, 5]
- 중복 체크 배열: [true, false, true, false, true]
- 출력: 1 3 5
- used[4] = false로 되돌림
두 번째 단계로 다시 복귀: depth = 1
- i의 값 증가 (i = 3)
- 선택 배열: [1, 4]
- 중복 체크 배열: [true, false, false, true, false]
- depth = 2로 이동
이를 계층 구조로 시각화하여 살펴보면 다음과 같다.
Main
└── permutation(0)
├── depth = 0, i = 0 (선택: [1])
│ └── permutation(1)
│ ├── depth = 1, i = 1 (선택: [1, 2])
│ │ └── permutation(2)
│ │ ├── depth = 2, i = 2 (선택: [1, 2, 3])
│ │ │ └── 출력: 1 2 3, 리턴, used[2] = false
│ │ ├── depth = 2, i = 3 (선택: [1, 2, 4])
│ │ │ └── 출력: 1 2 4, 리턴, used[3] = false
│ │ └── depth = 2, i = 4 (선택: [1, 2, 5])
│ │ └── 출력: 1 2 5, 리턴, used[4] = false
│ │
│ ├── depth = 1, i = 2 (선택: [1, 3])
│ │ └── permutation(2)
│ │ ├── depth = 2, i = 0 (건너뜀, used[0] = true)
│ │ ├── depth = 2, i = 1 (선택: [1, 3, 2])
│ │ │ └── 출력: 1 3 2, 리턴, used[1] = false
│ │ ├── depth = 2, i = 3 (선택: [1, 3, 4])
│ │ │ └── 출력: 1 3 4, 리턴, used[3] = false
│ │ └── depth = 2, i = 4 (선택: [1, 3, 5])
│ │ └── 출력: 1 3 5, 리턴, used[4] = false
│ │
│ └── depth = 1, i = 3 (선택: [1, 4])
│ └── permutation(2)
│ ├── depth = 2, i = 0 (건너뜀, used[0] = true)
│ ├── depth = 2, i = 1 (선택: [1, 4, 2])
│ │ └── 출력: 1 4 2, 리턴, used[1] = false
│ ├── depth = 2, i = 2 (선택: [1, 4, 3])
│ │ └── 출력: 1 4 3, 리턴, used[2] = false
│ └── depth = 2, i = 4 (선택: [1, 4, 5])
│ └── 출력: 1 4 5, 리턴, used[4] = false
│
└── 이하 동일한 패턴으로 계속...
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 2118 두 개의 탑 (JAVA 자바 풀이) (1) | 2024.01.02 |
|---|---|
| 백준 11725 트리의 부모 찾기 (JAVA 자바 풀이) (0) | 2023.12.31 |
| 백준 2504 괄호의 값 (JAVA 자바 풀이) (1) | 2023.12.31 |
| 백준 1406 에디터 (JAVA 자바 풀이) (0) | 2023.12.28 |
| 백준 1158 요세푸스 문제 (JAVA 자바 풀이) (0) | 2023.12.28 |
