πŸ”’ λ°±μ€€ 15656번 - Nκ³Ό M (7)

μ—…λ°μ΄νŠΈ:
2 λΆ„ μ†Œμš”

πŸ”’ λ°±μ€€ 15656번 - Nκ³Ό M (7)

λ°±μ€€ 둜고


βœ… 문제 μš”μ•½

  • N개의 μžμ—°μˆ˜ μ€‘μ—μ„œ 쀑볡을 ν—ˆμš©ν•˜μ—¬ M개λ₯Ό 고름
  • μ„ νƒν•œ μˆ˜μ—΄μ€ 사전 순으둜 좜λ ₯
  • 즉, 쀑볡 μˆœμ—΄ + μ •λ ¬λœ 좜λ ₯

alt alt


πŸ“₯ 예제 μž…λ ₯

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);
        }
    }
}

νƒœκ·Έ: , , , , , , , ,

μΉ΄ν…Œκ³ λ¦¬:

μ—…λ°μ΄νŠΈ:

λŒ“κΈ€λ‚¨κΈ°κΈ°