[백준/Java] 15649번 N과M(1)~(4)

문제

N과M(1) : https://www.acmicpc.net/problem/15649
N과M(2) : https://www.acmicpc.net/problem/15650
N과M(3) : https://www.acmicpc.net/problem/15651
N과M(4) : https://www.acmicpc.net/problem/15652

---

N과 M(1)

동작 방식

• arr와 visit의 초기 상태:
  • arr = [0, 0]
  • visit = [false, false, false]

DFS의 실행 과정:

1. depth = 0에서 i = 0:
   • visit = [true, false, false]
   • arr = [1, 0]
   • dfs(3, 2, 1) 호출
2. depth = 1에서 i = 1:
   • visit = [true, true, false]
   • arr = [1, 2]
   • dfs(3, 2, 2) 호출 -> 출력 1 2
   • visit = [true, false, false]로 복구
3. depth = 1에서 i = 2:
   • visit = [true, false, true]
   • arr = [1, 3]
   • dfs(3, 2, 2) 호출 -> 출력 1 3
   • visit = [true, false, false]로 복구
4. depth = 0에서 i = 1:
   • visit = [false, true, false]
   • arr = [2, 0]
   • dfs(3, 2, 1) 호출
5. depth = 1에서 i = 0:
   • visit = [true, true, false]
   • arr = [2, 1]
   • dfs(3, 2, 2) 호출 -> 출력 2 1
   • visit = [false, true, false]로 복구
6. depth = 1에서 i = 2:
   • visit = [false, true, true]
   • arr = [2, 3]
   • dfs(3, 2, 2) 호출 -> 출력 2 3
   • visit = [false, true, false]로 복구
7. depth = 0에서 i = 2:
   • visit = [false, false, true]
   • arr = [3, 0]
   • dfs(3, 2, 1) 호출
8. depth = 1에서 i = 0:
   • visit = [true, false, true]
   • arr = [3, 1]
   • dfs(3, 2, 2) 호출 -> 출력 3 1
   • visit = [false, false, true]로 복구
9. depth = 1에서 i = 1:
   - visit = [false, true, true]
   - arr = [3, 2]
   - dfs(3, 2, 2) 호출 -> 출력 3 2
   - visit = [false, false, true]로 복구

나의 코드

import java.util.Scanner;

public class Main {

    public static int[] arr;
    public static boolean[] visited;
    static Scanner sc = new Scanner(System.in);

    static int N = sc.nextInt();
    static int M = sc.nextInt();

    public static void main(String[] args) {
        arr = new int[M];
        visited = new boolean[N];
        dfs(0);
    }

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

        for(int i = 0; i < N; i ++){
            if(!visited[i]){
                visited[i] = true;
                arr[depth] = i + 1;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}

---

N과 M(2)

import java.util.Scanner;

public class Main {

    public static int[] arr;
    public static boolean[] visited;
    static Scanner sc = new Scanner(System.in);

    static int N = sc.nextInt();
    static int M = sc.nextInt();

    public static void main(String[] args) {
        arr = new int[M];
        visited = new boolean[N];
        dfs(0, 1);
    }

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

        for(int i = start - 1; i < N; i ++){
            if(!visited[i]){
                visited[i] = true;
                arr[depth] = i + 1;
                dfs(depth + 1, i + 1);
                visited[i] = false;
            }
        }
    }
}

---

N과 M(3)

import java.util.Scanner;

public class Main {

    public static int[] arr;
    public static boolean[] visited;
    static Scanner sc = new Scanner(System.in);
    static StringBuilder sb = new StringBuilder();
    static int N = sc.nextInt();
    static int M = sc.nextInt();

    public static void main(String[] args) {
        arr = new int[M];
        visited = new boolean[N];
        dfs(0);
        System.out.println(sb);
    }

    public static void dfs(int depth){
        if(depth == M){
            for(int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

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

---

N과 M(4)

import java.util.Scanner;

public class Main {

    public static int[] arr;
    public static boolean[] visited;
    static Scanner sc = new Scanner(System.in);
    static StringBuilder sb = new StringBuilder();
    static int N = sc.nextInt();
    static int M = sc.nextInt();

    public static void main(String[] args) {
        arr = new int[M];
        visited = new boolean[N];
        dfs(0, 1);
        System.out.println(sb);
    }

    public static void dfs(int depth, int start){
        if(depth == M){
            for(int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

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