TIL 2022-04-23-토

1. 오늘 학습한 내용

백준 백트래킹 문제 15649번 문제

• 문제

2. 알게 된 내용

백트래킹이란?

게임에서 선택지를 선택하고, 끝까지 한번 가본 후 다시 이 선택지점으로 돌아와서 다른 선택지를 선택해서 가보는 것이라고 생각하면 된다.
어떤 노드의 '유망성'을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법이다. 즉, 모든 경우의 수를 찾아보지만, 그 중에서도 가능성만 있는 경우의 수만 찾아보는 방법이다.
백트래킹의 종류 중 하나가 DFS이다.

이 문제의 해결 포인트

DFS로 구현하면 되는 문제인데, 1 ~ N까지의 각 수를 방문했는지 여부를 담는 visit 배열이 필요하고 이번에 출력할 수열을 담는 arr 배열이 필요하다. 이 두 배열에 값을 변경하면서 진행한다.
몇 번째 수를 담을지에 대한, (트리에서의 레벨같은) depth 변수도 필요하다.

static boolean[] visit; // 1 ~ N까지의 각 수를 방문했는지 여부
    static int[] arr;       // 이번에 출력할 수열을 담는 배열

    public static void dfs(int N, int M, int depth) {
        // 재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
        if (depth == M) {
            for (int val : arr) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < N; i++) {
            // 만약 해당 노드(값)을 방문하지 않았다면?
            if (visit[i] == false) {
                visit[i] = true;    // 해당 노드를 방문 상태로 변경
                arr[depth] = i + 1; // 해당 깊이를 index로 하여 i+1값 저장
                dfs(N, M, depth + 1); // 다음 자식 노드 방문을 위해 depth 1 증가시키면서 재귀호출

                // 자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
                visit[i] = false;
            }
        }
    }

출처 : https://st-lab.tistory.com/114
https://www.youtube.com/watch?v=Enz2csssTCs