[이때안] 알고리즘 - 백트래킹(Backtracking) JAVA | 백준 15649

 

 

알고리즘 1도 모르는 내가 시작하는 새로운 콘텐츠

'이해할 때까지 안 잔다.'

 

첫 번째 알고리즘은 백트래킹(backtracking)이다.

말 그대로 다시 돌아가서 트래킹 하는 것을 반복하는 것인데, 

 

특정 조건을 만족하기 전까지 모든 경우의 수를 탐색하고,

조건이 만족되었을 때 멈춰 재귀방식으로 다음 케이스를 탐색하는 것이다.

 

백트래킹의 기본 틀

public static void backtracking(int depth) {
    if(depth == M) {
        // 해당 depth에서 조합이 완료되었을 때, 처리 코드 작성
        return;
    }

    for(int i = 0; i < N; i++) {
            // N: int 배열과 같은 문제의 핵심 모델
            // backtracking() 재귀, 모든 조합을 탐색하기 위해 현재 depth 다음 것과의 조합을 진행 
            backtracking(depth + 1);
        }			
    }		
}

 

 

간단한 예시로 백트래킹을 익혀보자.

 

예시 1. N과 M

 

예를 들어, 자연수 3(N), 2(M)이 주어진다면 1~3 중 2개를 뽑아 나올 수 있는 모든 조합을 다 출력하는 것이다.

[1,2] [1,3] [2,1] [2,3] [3,1] [3,2] 이렇게 6개의 조합이 나온다.

이것을 공백으로 구분해서 출력하는 문제다.

 

구현 방식을 크게 살펴보자면,

모든 경우의 수를 하나씩 찾아가야 하기 때문에 재귀 함수를 쓸 것이고 → backtracking 알고리즘의 핵심

중복은 불가하니 재귀할 때마다 조합이 가능한 것인지 확인할 것이다. → visited 변수

그렇게 조합된 것들을 반환하여 출력한다. → model 변수

 

접근 방식

1) N과 M을 활용한 초기화

자연수의 범위를 정하는 N만큼 visited 크기를 할당해 준다.

또한 N개 중 M개를 뽑은 수열을 반환해야 하므로  M만큼 model의 크기를 할당해 준다.

public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        model = new int[M];
        visited = new boolean[N];

        backtracking(0);
        System.out.println(sb);

}

 

2) backtracking() 변수 depth는 현재 어느 곳을 돌고 있는지 확인하는 변수로,

재귀 함수의 종료 시점을 판단하는 중요한 변수이다. 

backtracking에서 기본적인 틀을 잡고 갈 때 depth 변수는 필수!!! 

 

* if문을 이해하기 전, for문으로 접근해 보자.

초기에 depth = 0으로 들어왔고, for문 내에서 i = 0일 때,

visited는 모두 false로 초기화되어 있으므로! visited [0] 조건에 만족하게 되고

 

만약 [1,2,3] 이 있다면 0번째 인덱스인 1이 시작 기점이 되어

1과 조합 가능한 숫자가 M개만큼 담겨 model에 저장된다.  

 

* if문을 이해해 보자.

M = 2라고 가정한다. 만약 model에 이미 [1,2]까지 찬 상태면

backtracking(depth + 1)로 backtracking(2)가 된 것이고, if문 조건에 해당된다.

 

따라서 model에 2개의 숫자 조합이 완성되었다는 것이므로 출력해 준다. 이때 재귀함수가 끝나게 된다. 

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

    for(int i = 0; i < N; i++) {
        if(!visited[i]) {
            visited[i] = true;
            model[depth] = i + 1;
            backtracking(depth + 1);

            visited[i] = false;
        }			
    }		
}

 

 

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	
    static int[] model;
    static boolean[] visited;
    static int N, M;
    public static StringBuilder sb = new StringBuilder();
	
	public static void backtracking(int depth) {
		if(depth == M) {
			for(int arr : model) {
				sb.append(arr).append(" ");
			}
			sb.append("\n");
			return;
		}

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

	public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            model = new int[M];
            visited = new boolean[N];

            backtracking(0);
            System.out.println(sb);
        
	}

}

 

 

백트래킹은 결국 0번째 인덱스부터 끝까지 하나씩 돌아가면서 인덱스를 고정해 나가며

가능한 모든 조합을 만드는 것이다.

 

기본 틀을 어느 정도 외워놔야 대입할 수 있겠구나 싶다.

일단 무조건 재귀함수를 멈추는 depth 체크 조건문이 있어야 한다는 점,

재귀함수 맨 처음 호출 시 (문제에서 특별한 조건이 없다면) 0번째 인덱스를 넘겨주고,

그다음 인덱스가 전달되게끔 +1과 같은 변화를 줘야 한다는 점..!

 

 

아직까진 완성된 백트래킹 코드를 보고 거꾸로 그림을 그려나가며 이해하는 단계지만

여러 문제를 풀다 보면 익숙해질 듯하다.

시간이 된다면 해당 코드를 그림으로 첨부해 놔야겠다.

 

조금 더 심화된 문제를 얼마 전에 강제적으로(?) 풀었는데 그 풀이도 같이 올려봐야겠다.

일단 이해 완료..

이해할 때까지 안 잔다 첫 번째 콘텐츠 오전 3시 7분 완료. 자자 . .. .. 

 

 

 

 

 

 

 

P.S.
뭔가 알긴 아는 것 같은데 제대로 설명이 안되어 있는 것 같다면... 네..맞습니다.

정확히 아는 거면 잘 설명하는데 어렴풋이 알아가는 단계에서 제가 이해한대로 표현하느라 서툴렀습니다.

이해가 잘 안되시거나 틀린 내용이 있거나.. 모든 피드백 감사하게 받겠습니다.

댓글이나 방명록에 남겨주세요. 열심히 공부해서 발전하는 모습 보여드리겠습니다:)

 

행복한 하루되세요.

 

 

 

 

참고 자료

https://www.youtube.com/watch?v=Ar40zcPoKEI&t=327s

https://stdio-han.tistory.com/93