๐ข ๋ฐฑ์ค 15656๋ฒ - N๊ณผ M (7)
๐ข ๋ฐฑ์ค 15656๋ฒ - N๊ณผ M (7)Permalink
โ ๋ฌธ์ ์์ฝPermalink
- N๊ฐ์ ์์ฐ์ ์ค์์ ์ค๋ณต์ ํ์ฉํ์ฌ M๊ฐ๋ฅผ ๊ณ ๋ฆ
- ์ ํํ ์์ด์ ์ฌ์ ์์ผ๋ก ์ถ๋ ฅ
- ์ฆ, ์ค๋ณต ์์ด + ์ ๋ ฌ๋ ์ถ๋ ฅ
๐ฅ ์์ ์ ๋ ฅPermalink
3 3
1231 1232 1233
- N = 3, M = 3
- ์ฌ์ฉ ๊ฐ๋ฅํ ์ซ์:
[1231, 1232, 1233]
๐ฏ ๋ชฉํ ์ถ๋ ฅPermalink
๋ชจ๋ ์ค๋ณต ์์ด์ ์ฌ์ ์์ผ๋ก ์ถ๋ ฅ:
1231 1231 1231
1231 1231 1232
1231 1231 1233
1231 1232 1231
...
1233 1233 1233
์ด ์ถ๋ ฅ ๊ฐ์: 3^3 = 27๊ฐ
๐ง DFS ๋ก์ง ๊ตฌ์กฐPermalink
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 ํ๋ฆ ์์Permalink
์์ ์ํPermalink
depth = 0
output = [_, _, _]
๊น์ด๋ณ ์ํ ๊ตฌ์กฐ (ํธ๋ฆฌ์ฒ๋ผ ์๊ฐ)Permalink
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์ค)Permalink
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
โ ํต์ฌ ํฌ์ธํธ ์์ฝPermalink
ํญ๋ชฉ | ์ค๋ช |
---|---|
์ค๋ณต ํ์ฉ | โ
๊ฐ๋ฅ (1231 1231 1231 ) |
์ค๋ฆ์ฐจ์ ์ถ๋ ฅ | โ
ํ์ (Arrays.sort() ์ฌ์ฉ) |
DFS ํ์ ๋ฐฉ์ | ๋งค depth๋ง๋ค ๋ชจ๋ input ๋ฐ๋ณต |
์ถ๋ ฅ ๊ฐ์ | NM = 33 = 27๊ฐ |
โ ์ค์ ์ฌ์ฉ ์ฝ๋ (Java)Permalink
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);
}
}
}
๋๊ธ๋จ๊ธฐ๊ธฐ