백트래킹(BackTracking, DFS/BFS), N과M(1)

백트래킹과 완전탐색에 대하여 헷갈려서 비교해보았다.

백트래킹은 특정 조건을 깔고 탐색하는방식.

 

백트래킹의 대표적인 요소 DFS, BFS.

DFS같은데??? ㅇㅇ맞음.

백준15649번: N과 M(1)

www.acmicpc.net/problem/15649

4C2를 통해 중복되지 않는 경우 나열.

DFS로 풀이한 방식이다.

import java.io.IOException;
import java.util.Scanner;

class Main {
    static int n, m;
    static int[] arr = new int[9];
    static boolean[] visited = new boolean[9];

    public static void main(String[] args) throws IOException {
        //input
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        comb(0);
    }

    static void comb(int k) {// 현재 k개까지 수를 택했음.
        if (k == m) {//끝까지 탐색했다면 출력.
            for (int i = 0; i < m; i++) {
                System.out.print(arr[i] + " ");
            }

            System.out.println();
            return;//한칸 위로 올라가기
        }
        for (int i = 1; i <= n; i++) {//1~N까지 수
            if (!visited[i]) {//사용되지않은 값 i에 대하여
                arr[k] = i;//arr[k]에 i값 저장
                visited[i] = true;//해당 i사용완료
                comb(k + 1);//사용한 i빼고 나머지에 대해서 재귀 ㄱㄱㄱ
                visited[i] = false;//사용했던거 다시 내려놓기 다른i탐색하러 ㄱㄱ
            }
        }
    }
}

 

comb메소드를 틀을 알아보자.

1. 매개변수 : 시작노드를 0으로 주지만, 결론적으로 arr에 노드에 해당값이 들어갈것이다. visited도 방문여부를 기록하는데 사용. 따라서 전역변수 arr[], visited[] 와 현재 몇개까지 뽑았는지 알려주는 k값(m값과 비교용)이 있다. N과M은 어차피 정적인 변수기때문에 전역으로 하던 매개로 하던 노상관.
2. 메소드를 끝내는 부분 : k==m(즉, m+1번 실행한것)일때 그동안 저장한 arr[]에 대하여 출력(단, 이때의 arr는 재귀의 한 뿌리에 불과하다.)
3. for문 시작 : 재귀 앞에서 사용할값 arr에 저장 및 방문true한걸로 미리 설정.
4. for문 중간 : 재귀(k+1)로 방문.
5. for문 끝 : 재귀 뒤에선 사용했었던거 반납. 방문안함으로 false

다음은 마지막 for문의 작동방식을 보여주는 예시이다.

123찍고 다시 돌아옴

124 경우 살펴보기

 

blog.encrypted.gg/945

[실전 알고리즘] 0x0C강 - 백트래킹