๐Ÿ”ข ๋ฐฑ์ค€ 15652๋ฒˆ - N๊ณผ M (4) (DFS/๋ฐฑํŠธ๋ž˜ํ‚น)

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

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

๋ฐฑ์ค€ ๋กœ๊ณ 


๐Ÿงฉ ๋ฌธ์ œ ์„ค๋ช…

  • ์ž์—ฐ์ˆ˜ N๊ณผ M์ด ์ฃผ์–ด์กŒ์„ ๋•Œ,
  • 1๋ถ€ํ„ฐ N๊นŒ์ง€ ์ž์—ฐ์ˆ˜ ์ค‘ M๊ฐœ๋ฅผ ๋ฝ‘๋˜, ๊ฐ™์€ ์ˆ˜๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ๊ณจ๋ผ๋„ ๋˜๊ณ 
  • ๋น„๋‚ด๋ฆผ์ฐจ์ˆœ(์˜ค๋ฆ„์ฐจ์ˆœ ํฌํ•จ)์ธ ์ˆ˜์—ด์„ ๋ชจ๋‘ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

alt alt


๐Ÿ’ก ๋ฌธ์ œ ์กฐ๊ฑด ์š”์•ฝ

์กฐ๊ฑด ๋‚ด์šฉ
์ˆซ์ž ๋ฒ”์œ„ 1 ~ N
๋ฝ‘๋Š” ๊ฐœ์ˆ˜ M๊ฐœ
์ค‘๋ณต ํ—ˆ์šฉ โœ… ๊ฐ€๋Šฅ
์ˆœ์„œ ์ค‘์š” โŒ ๋น„๋‚ด๋ฆผ์ฐจ์ˆœ๋งŒ ํ—ˆ์šฉ
์ •๋ ฌ ์˜ค๋ฆ„์ฐจ์ˆœ ๋˜๋Š” ๊ฐ™์€ ์ˆซ์ž ํ—ˆ์šฉ (ex. 1 1 2, 2 2 2 ๊ฐ€๋Šฅ)

๐Ÿ“ฅ ์ž…๋ ฅ ์˜ˆ์‹œ

3 2

๐Ÿ“ค ์ถœ๋ ฅ ์˜ˆ์‹œ

1 1
1 2
1 3
2 2
2 3
3 3

๐Ÿง  ํ•ต์‹ฌ ์•„์ด๋””์–ด

์ด ๋ฌธ์ œ๋Š” โ€œ์ค‘๋ณต ์กฐํ•ฉ (Combination with Repetition)โ€ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

  • ์ค‘๋ณต์€ ํ—ˆ์šฉ๋˜์ง€๋งŒ ์ˆœ์„œ๋งŒ ์ •๋ ฌ๋œ ํ˜•ํƒœ์—ฌ์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— start ๊ฐ’์„ ์žฌ๊ท€๋กœ ๋„˜๊ฒจ์ฃผ๋ฉฐ ์˜ค๋ฆ„์ฐจ์ˆœ์„ ์œ ์ง€ํ•ฉ๋‹ˆ๋‹ค.
  • ์ฆ‰, ์ด์ „์— ์„ ํƒํ•œ ์ˆซ์ž ์ด์ƒ๋ถ€ํ„ฐ๋งŒ ๋‹ค์‹œ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋„๋ก ํ•ฉ๋‹ˆ๋‹ค.

โœ… Java ์ฝ”๋“œ ํ’€์ด

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Back_15652 {
    public static int[] arr;
    public static int N, M;

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

        arr = new int[M];

        dfs(1, 0); // 1๋ถ€ํ„ฐ ์‹œ์ž‘, ๊นŠ์ด๋Š” 0
    }

    private static void dfs(int start, int depth) {

        if (depth == M) {
            for (int i : arr)
                System.out.print(i + " ");
            System.out.println();
            return;
        }

        for (int i = start; i <= N; i++) {
            arr[depth] = i;        // ํ˜„์žฌ ์œ„์น˜์— ์ˆซ์ž ์ €์žฅ
            dfs(i, depth + 1);     // ์ค‘๋ณต ํ—ˆ์šฉ โ†’ i๋ถ€ํ„ฐ ๋‹ค์‹œ ํƒ์ƒ‰
        }
    }
}

๐Ÿ” ์ฝ”๋“œ ํ•ด์„ค

1๏ธโƒฃ dfs(start, depth) ํ•จ์ˆ˜

๋งค๊ฐœ๋ณ€์ˆ˜ ์˜๋ฏธ
start ํ˜„์žฌ ์„ ํƒ ๊ฐ€๋Šฅํ•œ ์ตœ์†Œ ์ˆซ์ž (์ค‘๋ณต ํ—ˆ์šฉ, ์˜ค๋ฆ„์ฐจ์ˆœ ์œ ์ง€)
depth ํ˜„์žฌ๊นŒ์ง€ ์„ ํƒํ•œ ์ˆ˜์˜ ๊ฐœ์ˆ˜ (M์— ๋„๋‹ฌํ•˜๋ฉด ์ถœ๋ ฅ)

2๏ธโƒฃ ๊ธฐ์ € ์กฐ๊ฑด

if (depth == M) {
    for (int i : arr) System.out.print(i + " ");
    System.out.println();
    return;
}
  • M๊ฐœ์˜ ์ˆ˜๋ฅผ ๋ชจ๋‘ ๊ณจ๋ž์œผ๋ฉด ํ˜„์žฌ ์กฐํ•ฉ์„ ์ถœ๋ ฅํ•˜๊ณ  return.

3๏ธโƒฃ ์ค‘๋ณต ์กฐํ•ฉ ๋กœ์ง

for (int i = start; i <= N; i++) {
    arr[depth] = i;
    dfs(i, depth + 1); // ์ค‘๋ณต ํ—ˆ์šฉ โ†’ i๋ถ€ํ„ฐ ์‹œ์ž‘
}
  • ์ค‘๋ณต ํ—ˆ์šฉ์ด๊ธฐ ๋•Œ๋ฌธ์— dfs(i, depth + 1)๋กœ ํ˜ธ์ถœ
  • ์ผ๋ฐ˜ ์ˆœ์—ด์ด๋ผ๋ฉด dfs(i + 1, ...)๋กœ ํ–ˆ๊ฒ ์ง€๋งŒ, ์—ฌ๊ธฐ์„œ๋Š” ๊ฐ™์€ ์ˆซ์ž๋„ ๋‹ค์‹œ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Œ

๐Ÿ“Œ ์‹œ๊ฐ„ ๋ณต์žก๋„

  • ์ตœ์•…์˜ ๊ฒฝ์šฐ O(N^M) ์ •๋„
  • N=7, M=7 ์ •๋„๊นŒ์ง€๋Š” ์ถฉ๋ถ„ํžˆ ํƒ์ƒ‰ ๊ฐ€๋Šฅ

โœ… ์ •๋ฆฌ

ํ•ญ๋ชฉ ์„ค๋ช…
๋ฌธ์ œ ์œ ํ˜• ๋ฐฑํŠธ๋ž˜ํ‚น + ์ค‘๋ณต ์กฐํ•ฉ
์ค‘๋ณต ํ—ˆ์šฉ O
์˜ค๋ฆ„์ฐจ์ˆœ ์œ ์ง€ O (start ์ด์šฉ)
DFS ํƒ์ƒ‰ ๋ฐฉ์‹ ํ˜„์žฌ ์ˆซ์ž๋ถ€ํ„ฐ ๋‹ค์‹œ ํƒ์ƒ‰ (์ค‘๋ณต ํ—ˆ์šฉ)

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