백준 15649 백트래킹 알고리즘 N과 M(1) 풀이

 

 

 

백준 15649 문제는 백트래킹 알고리즘을 다룬다. 트리 형태로 만들어진 노드들을 순회하면서 가장 유망한 노드를 선택하여 연산을 진행한다. 이 후 부모 노드로 돌아와서 새로운 노드를 찾아나서는 구조다.

 

노드를 순회하기 위해서는 재귀함수를 사용해야 한다. 재귀함수에는 탈출조건을 추가해줘야 한다. 현재 노드를 기억하기 위해서 depth 변수를 사용해서 탈출조건값을 만족시킨다. 노드가 순회하는 과정을 총 18단계에 걸쳐서 자세히 살펴본다.

 

초기단계

N은 자연수의 크기 = 3

M은 자연수 내의 수열 = 2

 

1단계

depth = 0

recur(0)함수를 호출한다.

최초 isVisited[]는 모두 false로 초기화 되어 있어  for문 안에서 arr[0]을 1로 변환한다.

recur(1) 함수를 호출한다.

 

2단계

depth=1

탈출조건을 아직 만족하지 못했다.

isVisited[0]은 이미 true로 설정되어 있기 때문에 isVisted[1]을 true로 바꾸고 arr[1]을 2로 변환한다.

recur(2) 함수를 호출한다.

 

3단계

depth=2

탈출조건을 만족했다. arr = {1,2} 설정된 value를 print 하고 현재 recur(2) 함수를 리턴한다.

 

4단계

depth=1

isVisited[1]을 false로 변환하고, 2단계의 i=2 for 문을 수행한다. arr[1]에 3을 할당한다.

recur(2) 함수를 호출한다.

 

5단계

depth=2

탈출조건이 만족했다. arr={1,3} 설정된 value를 print 하고 현재 recur(2)함수를 리턴한다.

2단계의 for문을 모두 돌았기 때문에 현재 recur(1)함수가 종료된다.

 

6단계

depth=0

1단계로 다시 복귀했다. isVisted[0]에 false를 할당한다. i=1이 된다. isVisted[1]을 true로 할당한다.

arr[0]에 2를 할당한다. recur(1) 함수를 호출한다.

 

7단계

depth=1

탈출조건을 만족하지 못했다.

isVisted[0]을 true로 할당한다.

arr[1]에 1을 할당한다. recur(2) 함수를 호출한다.

 

8단계

depth=2

탈출조건을 만족했다.(depth(2)=M(2))

arr={2,1}을 print 하고 리턴한다.

 

9단계

7단계로 복귀한다.

depth=1

isVisited[1]은 true로 할당되어 있기 때문에 isVisited[2]을 false로 할당한다. i=2가 된다.

isVisited[2]를 true로 할당한다.

arr[1]에 3을 할당한다.

recur(2) 함수를 호출한다.

 

10단계

depth=2

탈출 조건을 만족했다.

arr={2,3}을 출력하고 리턴한다.

 

11단계

depth=1

9단계로 복귀한다.

isVisited[2]를 false로 변경하고 for문을 종료한다.

 

12단계

6단계로 복귀한다.

depth=0, i=2가 된다.

isVisited[2]를 true로 할당한다. arr[0]에 3을 할당한다.

recur(1)함수를 호출한다.

 

13단계

depth=1

탈출조건을 만족하지 못한다. i=0부터 for문을 순회한다.

isVisited[0]을 true로 할당한다. arr[1]에 1을 할당한다.

recur(2)함수를 호출한다.

 

14단계

depth=2

탈출조건을 만족한다. arr={3,1}를 print 한 후 리턴한다.

 

15단계

depth=1

isVisited[0]을 false로 변경한다. i=1이 된다.

isVisited[1]을 true로 할당한다. arr[1]에 2를 할당한다.

recur(2) 함수를 호출한다.

 

16단계

depth=2

탈출조건을 만족한다. arr={3,2}를 print 한 후 return 한다.

 

17단계

depth=1

isVisited[1]을 false로 변경한다. i=2이 된다.

isVisited[2]는 true로 할당되어 있기 때문에 for문을 종료한다.

 

18단계

depth=0

isVisited[2]를 false로 할당하고 for문을 종료한다.

프로그램이 종료된다.

 

JAVA 코드

import java.util.Scanner;

public class back_tracking {
    public static int[] arr;
    public static boolean[] isVisited;
    public static int N;
    public static int M;

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

        // N과 M을 입력받는다.
        N = in.nextInt();
        M = in.nextInt();

        // M 크기의 Integer 배열 생성
        arr = new int[M];
        // N 크기의 Boolean 배멸 생성
        isVisited = new boolean[N];
    
        recur(0);
    }

    public static void recur(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(!isVisited[i]){
                isVisited[i] = true;
                arr[depth] = i+1;
                recur(depth+1);
                isVisited[i] = false;
            }
        }
    }
}

 

 

백준 15649번 N과M(1) 풀이 후기

노드 형식으로 만들어진 테이블을 순회하면서 자식노드 부모노드를 depth로 표시해가면서 순열의 값들을 하나씩 채워간다. 이해가 안될 때는 글로 적어보면서 이해하는게 훨씬 빠르다. 3*2 테이블의 경우 0 -> 1 -> 2 -> 1->2 의 의 순서가 계속해서 반복된다. 

 

만약 4*2의 테이블이면 0->1->2->1->2->1->2 이 될 것이다.