π’ λ°±μ€ 15656λ² - Nκ³Ό M (7)
π’ λ°±μ€ 15656λ² - Nκ³Ό M (7)
β λ¬Έμ μμ½
- Nκ°μ μμ°μ μ€μμ μ€λ³΅μ νμ©νμ¬ Mκ°λ₯Ό κ³ λ¦
- μ νν μμ΄μ μ¬μ μμΌλ‘ μΆλ ₯
- μ¦, μ€λ³΅ μμ΄ + μ λ ¬λ μΆλ ₯
π₯ μμ μ λ ₯
3 3
1231 1232 1233
- N = 3, M = 3
- μ¬μ© κ°λ₯ν μ«μ:
[1231, 1232, 1233]
π― λͺ©ν μΆλ ₯
λͺ¨λ μ€λ³΅ μμ΄μ μ¬μ μμΌλ‘ μΆλ ₯:
1231 1231 1231
1231 1231 1232
1231 1231 1233
1231 1232 1231
...
1233 1233 1233
μ΄ μΆλ ₯ κ°μ: 3^3 = 27κ°
π§ DFS λ‘μ§ κ΅¬μ‘°
void dfs(int depth) {
if (depth == M) {
print(output);
return;
}
for (int i = 0; i < N; i++) {
output[depth] = input[i];
dfs(depth + 1);
}
}
depth
λ νμ¬κΉμ§ μ νν μ«μμ κ°μoutput[depth]
μ κ°μ λ£κ³ , λ€μ μ«μλ₯Ό μ νdepth == M
μ΄ λλ©΄ μΆλ ₯
π DFS νλ¦ μμ
μμ μν
depth = 0
output = [_, _, _]
κΉμ΄λ³ μν ꡬ쑰 (νΈλ¦¬μ²λΌ μκ°)
depth = 0
ββ 1231 β dfs(1)
β ββ 1231 β dfs(2)
β β ββ 1231 β dfs(3) β μΆλ ₯: 1231 1231 1231
β β ββ 1232 β dfs(3) β μΆλ ₯: 1231 1231 1232
β β ββ 1233 β dfs(3) β μΆλ ₯: 1231 1231 1233
β ββ 1232 β dfs(2)
β β ββ 1231 β μΆλ ₯: 1231 1232 1231
β β ββ 1232 β μΆλ ₯: 1231 1232 1232
β β ββ 1233 β μΆλ ₯: 1231 1232 1233
β ββ 1233 β dfs(2)
β ββ 1231 β μΆλ ₯: 1231 1233 1231
β ββ 1232 β μΆλ ₯: 1231 1233 1232
β ββ 1233 β μΆλ ₯: 1231 1233 1233
ββ 1232 β dfs(1)
β ββ ...
ββ 1233 β dfs(1)
ββ ...
β μ΅μ’ μΆλ ₯ κ²°κ³Ό (μ΄ 27μ€)
1231 1231 1231
1231 1231 1232
1231 1231 1233
1231 1232 1231
1231 1232 1232
1231 1232 1233
1231 1233 1231
1231 1233 1232
1231 1233 1233
1232 1231 1231
1232 1231 1232
1232 1231 1233
1232 1232 1231
1232 1232 1232
1232 1232 1233
1232 1233 1231
1232 1233 1232
1232 1233 1233
1233 1231 1231
1233 1231 1232
1233 1231 1233
1233 1232 1231
1233 1232 1232
1233 1232 1233
1233 1233 1231
1233 1233 1232
1233 1233 1233
β ν΅μ¬ ν¬μΈνΈ μμ½
νλͺ© | μ€λͺ |
---|---|
μ€λ³΅ νμ© | β
κ°λ₯ (1231 1231 1231 ) |
μ€λ¦μ°¨μ μΆλ ₯ | β
νμ (Arrays.sort() μ¬μ©) |
DFS νμ λ°©μ | λ§€ depthλ§λ€ λͺ¨λ input λ°λ³΅ |
μΆλ ₯ κ°μ | NM = 33 = 27κ° |
β μ€μ μ¬μ© μ½λ (Java)
import java.io.*;
import java.util.*;
public class Back_15656 {
static int N, M;
static int[] input, output;
static StringBuilder sb = new StringBuilder();
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());
input = new int[N];
output = new int[M];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(input); // μ¬μ μ μΆλ ₯μ μν μ λ ¬
dfs(0);
System.out.print(sb);
}
static void dfs(int depth) {
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(output[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
output[depth] = input[i];
dfs(depth + 1);
}
}
}
λκΈλ¨κΈ°κΈ°