๐Ÿ”ข ๋ฐฑ์ค€ 15656๋ฒˆ - N๊ณผ M (7)

์—…๋ฐ์ดํŠธ:
2 ๋ถ„ ์†Œ์š”

๐Ÿ”ข ๋ฐฑ์ค€ 15656๋ฒˆ - N๊ณผ M (7)Permalink

๋ฐฑ์ค€ ๋กœ๊ณ 


โœ… ๋ฌธ์ œ ์š”์•ฝPermalink

  • N๊ฐœ์˜ ์ž์—ฐ์ˆ˜ ์ค‘์—์„œ ์ค‘๋ณต์„ ํ—ˆ์šฉํ•˜์—ฌ M๊ฐœ๋ฅผ ๊ณ ๋ฆ„
  • ์„ ํƒํ•œ ์ˆ˜์—ด์€ ์‚ฌ์ „ ์ˆœ์œผ๋กœ ์ถœ๋ ฅ
  • ์ฆ‰, ์ค‘๋ณต ์ˆœ์—ด + ์ •๋ ฌ๋œ ์ถœ๋ ฅ

alt alt


๐Ÿ“ฅ ์˜ˆ์ œ ์ž…๋ ฅ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);
        }
    }
}

ํƒœ๊ทธ: , , , , , , , ,

์นดํ…Œ๊ณ ๋ฆฌ:

์—…๋ฐ์ดํŠธ:

๋Œ“๊ธ€๋‚จ๊ธฐ๊ธฐ