최근 백트래킹 문제를 몇개를 풀었지만, 도저히 감을 잡기가 어려워서 단어변환 문제를 풀다가 해당 문제를 바탕으로 백트래킹의 동작방식을 알 수 있는 예제를 혼자서 한번 만들어보기로 했다.
문제
목적지 target 인 D 와 arr 배열에 {A, B, C, D}의 문자열이 있다고 했을 때, 어디서 출발을 해야 가장 빠르게 목적지인 target D로 도착할 수 있을지 알아보자.
즉, A, B, C, D의 각 값이 길이라고 했을 때, 문자열 A, B, C, D중 어떤 길을 선택해야 가장 target에 빠르게 도착할까?
생각하기
문제가 너무 쉽다.
당연히 target이 D이고, arr에 D가 있는데 누가봐도 D 에서 출발하면 그냥 도착이긴하다.
보통 이정도였으면 뭐.. 쉽게 풀었을 테지만, 이 문제는 백트래킹을 통해서 문제를 해결하는 것이 포인트이다.
동작
당연히 결과 값은 D로 result가 1일 것을 알지만, 과정이 핵심이므로 과정을 봐주길 바란다.
위에서 말했듯이 우리가 만든 배열 arr은 구간을 말하기때문에, 어떤 곳에서 출발했을때, 가장 빠르게 도달 할 수 있을까를 알아야 한다.
출력으로 알 수 있게 List를 따로 만들어서 완성된 루트를 List로 출력해보았다.
마지막 결과 출력 값
재귀 실행 DFS(A, 0)
재귀 실행 DFS(A, 1)
재귀 실행 DFS(B, 2)
재귀 실행 DFS(C, 3)
재귀 실행 DFS(D, 4)
result : 4
List : [A, B, C, D]
재귀 탈출 현재 DFS(D, 3)
재귀 탈출 현재 DFS(C, 2)
재귀 실행 DFS(D, 3)
result : 3
List : [A, B, D]
재귀 탈출 현재 DFS(D, 2)
재귀 탈출 현재 DFS(B, 1)
재귀 실행 DFS(C, 2)
재귀 실행 DFS(B, 3)
재귀 실행 DFS(D, 4)
result : 3
List : [A, C, B, D]
재귀 탈출 현재 DFS(D, 3)
재귀 탈출 현재 DFS(B, 2)
재귀 실행 DFS(D, 3)
result : 3
List : [A, C, D]
재귀 탈출 현재 DFS(D, 2)
재귀 탈출 현재 DFS(C, 1)
재귀 실행 DFS(D, 2)
result : 2
List : [A, D]
재귀 탈출 현재 DFS(D, 1)
재귀 탈출 현재 DFS(A, 0)
재귀 실행 DFS(B, 1)
재귀 실행 DFS(A, 2)
재귀 실행 DFS(C, 3)
재귀 실행 DFS(D, 4)
result : 2
List : [B, A, C, D]
재귀 탈출 현재 DFS(D, 3)
재귀 탈출 현재 DFS(C, 2)
재귀 실행 DFS(D, 3)
result : 2
List : [B, A, D]
재귀 탈출 현재 DFS(D, 2)
재귀 탈출 현재 DFS(A, 1)
재귀 실행 DFS(C, 2)
재귀 실행 DFS(A, 3)
재귀 실행 DFS(D, 4)
result : 2
List : [B, C, A, D]
재귀 탈출 현재 DFS(D, 3)
재귀 탈출 현재 DFS(A, 2)
재귀 실행 DFS(D, 3)
result : 2
List : [B, C, D]
재귀 탈출 현재 DFS(D, 2)
재귀 탈출 현재 DFS(C, 1)
재귀 실행 DFS(D, 2)
result : 2
List : [B, D]
재귀 탈출 현재 DFS(D, 1)
재귀 탈출 현재 DFS(B, 0)
재귀 실행 DFS(C, 1)
재귀 실행 DFS(A, 2)
재귀 실행 DFS(B, 3)
재귀 실행 DFS(D, 4)
result : 2
List : [C, A, B, D]
재귀 탈출 현재 DFS(D, 3)
재귀 탈출 현재 DFS(B, 2)
재귀 실행 DFS(D, 3)
result : 2
List : [C, A, D]
재귀 탈출 현재 DFS(D, 2)
재귀 탈출 현재 DFS(A, 1)
재귀 실행 DFS(B, 2)
재귀 실행 DFS(A, 3)
재귀 실행 DFS(D, 4)
result : 2
List : [C, B, A, D]
재귀 탈출 현재 DFS(D, 3)
재귀 탈출 현재 DFS(A, 2)
재귀 실행 DFS(D, 3)
result : 2
List : [C, B, D]
재귀 탈출 현재 DFS(D, 2)
재귀 탈출 현재 DFS(B, 1)
재귀 실행 DFS(D, 2)
result : 2
List : [C, D]
재귀 탈출 현재 DFS(D, 1)
재귀 탈출 현재 DFS(C, 0)
재귀 실행 DFS(D, 1)
result : 1
List : [D]
재귀 탈출 현재 DFS(D, 0)
최종 정답 : 1
출력 결과 값에서 List를 보면,
배열 arr에 있는 각 원소들로 target인 D까지 가기 위해서 어떤 경로로 가야 최소한의 경로로 이동하는지 탐색하는 과정을 볼 수 있다.
이번에는 List의 출력된 값만 모아서 보자.
List 만 출력
List : [A, B, C, D]
List : [A, B, D]
List : [A, C, B, D]
List : [A, C, D]
List : [A, D]
List : [B, A, C, D]
List : [B, A, D]
List : [B, C, A, D]
List : [B, C, D]
List : [B, D]
List : [C, A, B, D]
List : [C, A, D]
List : [C, B, A, D]
List : [C, B, D]
List : [C, D]
List : [D]
최종 정답 : 1
이렇게 전체 List의 결과를 모두 몰아서 보니까 이제 대충 그림이 그려진다.
DFS탐색을 하면서 arr을 통해 D로 갈 수 있는 모든 경로를 탐색한다.
결국 갈 수 있는 모든 경우의 수를 구하는 것이다.
- A에서 출발해서 D로 갈 수 있는 모든 경우,
- B에서 출발해서 D로 갈 수 있는 모든 경우,
- C에서 출발해서 D로 갈 수 있는 모든 경우,
- D에서 출발해서 D로 갈 수 있는 모든 경우,
총 16가지의 경우 중, 가장 짧은 값 하나를 뽑아 내는 것
여기서 지나온 값을 다시 검증하고, List에 겹치는 알파벳이 들어가지 않도록 해주는 장치가 바로 백트래킹 장치이다.
for(int i=0; i<arr.length; i++) {
if(visit[i]) continue;
list.add(arr[i] );
visit[i] = true;
DFS(arr[i], count + 1);
System.out.println("재귀 탈출 현재 DFS(" + arr[i] + ", " + count + ")");
visit[i] = false;
list.pollLast();
}위 코드처럼 백트래킹은 계속 되는 무한 루프를 막기위해서 DFS의 재귀 탈출 조건과 상관없이 반복문 안에서 백트래킹을 하도록 만들어진다.
이렇게 하면, visit의 true, false 여부와 관련없이 i값이 더 이상 증가할 수 없기 때문에, for문에서 종료가 되는 것이다.
arr의 알파벳을 통해 나열 할 수 있는 전체 경우의 수를 탐색하는 것과 비슷함
재귀가 종료되어 이전 재귀로 돌아왔을 때 내가 사용했던 arr의 알파벳은 다시 제자리로 돌려놓고, 다음 재귀 함수에서 해당 알파벳을 사용하는 것이다.
마치 도서관의 도서 대출, 반납 과정과 비슷한 것 같음.
한명이 책을 빌려갔을 경우, 해당 책은 도서관에 없기 때문에 해당 책을 읽고 싶은 사람은 그 사람이 반납을 할 때까지 기다려야 한다.
시간이 지나서 책을 빌렸던 사람이 반납을 해서 사서가 다시 그자리 돌려놓는다면, 이제는 해당 책을 빌릴 수 있기 때문에 기다리던 사람이 그 책을 다시 대출해서 돌려놓는다.
이 과정이 visit의 배열이다. 책을 빌려간 사람은 true값으로 돌려놓고 책을 다 읽은 뒤에는 다시 반납하면서 false로 돌려놓고 사용이 가능하다는 것을 표시하는 것이다.
그리고 마지막에는 전체가 false가 되어있을 것이다.
개인적인 생각이지만, 온라인 저지 문제에 알고리즘을 활용하거나 기초적인 문제가 많이 있긴하지만, 이런 정말 근본적이면서, 구동 방식에 대해 알 수 있는 문제도 많았으면 좋겠다는 생각을 늘 했었다.
이 예제를 만들어보면서 느낀점은, 알고리즘 별로 기초를 다질 수 있는 문제를 몇개 더 만들어보면 좋을 것 같다는 생각을 해보았다.
코드
import java.util.*; public class Main_백트래킹예제 { static String target; static String[] arr = {"A", "B", "C", "D"}; static boolean[] visit; static int result = Integer.MAX_VALUE; static LinkedList<String> list = new LinkedList<>(); public static void main(String[] args) { target = "D"; visit = new boolean[4]; // target인 D까지 갈 수 있는 최소한의 값을 구하여라 DFS(arr[0], 0); System.out.println("최종 정답 : " + result); } // End of main static void DFS(String begin, int count) { System.out.println("재귀 실행 DFS(" + begin + ", " + count + ")"); if(begin == target) { result = Math.min(result, count); System.out.println("result : " + result); System.out.println( "List : " + list); System.out.println("\n"); return; } for(int i=0; i<arr.length; i++) { if(visit[i]) continue; list.add(arr[i] ); visit[i] = true; DFS(arr[i], count + 1); System.out.println("재귀 탈출 현재 DFS(" + arr[i] + ", " + count + ")"); visit[i] = false; list.pollLast(); } } // End of DFS } // End of main
