[백준] 15649번 N과 M(1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

	최초 depth		자기 자신의 index는 visit = true 로 패스
i = 0	arr[0] = 1	i = 0	pass
		i = 1	arr[1] = 2
		i = 2	arr[1] = 3
		i = 3	arr[1] = 4
i = 1	arr[0] = 2	i = 0	arr[1] = 1
		i = 1	pass
		i = 2	arr[1] = 3
		i = 3	arr[1] = 4
i = 2	arr[0] = 3	i = 0	arr[1] = 1
		i = 1	arr[1] = 2
		i = 2	pass
		i = 3	arr[1] = 4
i = 3	arr[0] = 4	i = 0	arr[1] = 1
		i = 1	arr[1] = 2
		i = 2	arr[1] = 3
		i = 3	pass

 

브루트포스 : 모든 경우의 수 판단

백트래킹 : 조건을 추가하여 해당 노드의 유망성 판단

DFS : 깊이 우선 탐색 - 백트래킹을 구현하는 방법 중 하나

 

import java.util.*;

public class Main {

    public static int N, M;
    public static boolean[] visit;
    public static int[] arr;
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 자연수
        M = sc.nextInt(); // 경우의 수
        visit = new boolean[N];
        arr = new int[M];
        dfs(0);
    }

    private static void dfs(int depth) {

        // 재귀 깊이가 경우의 수(M)과 같아지면 출력하고 dfs 리턴
        if(depth == M) {
            for(int num : arr) {
            	System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for(int i = 0; i < N; i++) {
            if(!visit[i]) {
                // i에 방문처리를 하여 내부 dfs에서 탐색하지 않도록 한다.
                visit[i] = true;

                arr[depth] = i + 1;
                dfs(depth+1);

                // dfs 한 회차 탐색이 끝나면 i의 방문처리 해제
                visit[i] = false;
            }
        }
    }
}