[JAVA] 백준 N과 M(2), DFS 중복X

N과M(1)은 중복 O

중복 허용

N과M(2)는 중복 X

중복제거

둘다 DFS를 활용한 코드이다.

 

오히려 중복없이 출력하는 코드인 (2)가 더 짧다.

단, 매개변수를 하나 더 필요로한다.

 

이 값(at)은 현재 index값보다 더 큰 index에 대하여 for문을 돌리기위해 사용한다.

import java.util.Scanner;

class Main {

    public static int[] arr;
    public static int N, M;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();

        arr = new int[M];
        dfs(1, 0);

    }

    public static void dfs(int at, int depth) {
        if (depth == M) {
            for (int val : arr) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }

        for (int i = at; i <= N; i++) {
            arr[depth] = i;
            dfs(i + 1, depth + 1);
        }
    }
}

예를들어서 at은 다음과 같을때 사용된다.

중복x일때는 visit가 필요없고 대신 인수하나 추가해서 인수 이상의 값만 탐색한다.

 

 

 

 

st-lab.tistory.com/115

[백준] 15650번 : N과 M (2) - JAVA [자바]