[Algorithm] 백트래킹(BackTracking) 알고리즘(feat_백준 15686번 치킨 배달_java)

안녕하세요. 신뇽이 되고싶은 미뇽입니다!

연구소 문제를 풀면서 이건 dfs인데,,? bfs?인데..? 뭘 사용해야하지,,,? 하다가 몇시간을 날렸습니다..

도저히 못풀겠어서 구글링을 했는데 bfs, dfs 모두 사용해야하더라고요!!

 

다른 사람들의 코드를 차근차근 보는 동안 이해가 되지 않는 부분이 있었습니다.

 

바로 아래 코드 부분이었습니다.

originalMap[i][j] = 0; 

 

 

 

 

 

알고 보니 이는 백트래킹이라는 알고리즘이었고,

백트래킹을 공부해야 제대로 이해할 수 있겠다 싶었기에 

백트래킹을 먼저 공부하자 했습니다!!

 

(저학년 때부터 백준 안풀어본 것에 대해 후회가 되네요,,)

 

 

 

 

 

연구소 문제 링크입니다! 

14502번: 연구소

 

 

 

백트래킹이란?

해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 해를 다시 찾아가는 기법을 말합니다.

 

DFS와 백트래킹(BackTracking)

DFS(Depth-First Search)

 

깊이 우선 탐색으로 가능한 모든 경로를 탐색합니다.

 

DFS의 단점인 해가 없는 경로에 깊이 빠질 가능성이 있습니다.

 

->  모든 경로를 탐색한다는 특징이 있어, 불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이지 못합니다. 

 

 

백트래킹(BackTracking)

알고리즘 기법 중 하나로 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상테가 위배되는 경우 해당 상태를 제외하고 다음 단계로 넘어갑니다.

 

쉽게 말하면, 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 다시 해를 찾는다라고 생각하시면 됩니다!

 

더 이상 탐색할 필요가 없는 상태를 제외한다는 것이 백트래킹의 핵심인데, 이를 가지치기라고 합니다.

 

DFS와 백트래킹의 관계

백트래킹은 모든 경우의 수에서 조건을 만족하는 경우를 탐색하는 것이기 떄문에 완전탐색 기법인 DFS, BFS로 모두 구현이 가능합니다

 

백트래킹 특성에서 조건에 부합하지 않으면 이전 수행으로 돌아가야 함으로 BFS보다는 DFS가 구현하기 더 편하기 때문에 주로 DFS를 사용합니다!

 

 

예시) 백준 15686번 치킨 배달

 

dfs부분만 빼서 오면

 

 

이렇게 됩니다.

현재 이 반복문의 구조가 어떻게 되어있냐면,

dfs 함수 안에 이 for문이 있습니다.

 

 

 

이해가 안가던 부분이 있었는데, 바로 open[i] = false; 부분이 왜 존재해야하는지였습니다.

 

디버깅을 해보면서 이해를 했는데, chicken.size()가 4라고 했을 때 

 

open 배열이 [true, true, false, flase]일때 검사해주고 

가장 마지막 true를 false로 바꿔주고  [true, false, true , flase]를 검사해주고 

또 가장 마지막 true를 false로 바꿔주고   [true, false, flase , true  ]를 검사해주기 위해서 입니다!

 

이때 배열의 인덱스 0번은 true로 고정입니다!!!

 

여기서 또 의문이 생겼습니다..! 

그러면 

[ false, true , true, flase ] [ false, true,  flase , true ] 이렇게는 또 어떻게 실행이 되는거지??

 

디버깅을 하며 이해를 해보려고 노력했습니다.. 쉽지 않더라고요,,

 

디버깅 했을 때도 이해가 안가는 부분이 있었는데, 바로

 

chicken.size()가 4라고 했을 때 i가 3까지 모두 돌고

DFS(i + 1, cnt + 1);
open[i] = false; //이떼 i는 가장 마지막의 true 인덱스

 위의 코드까지 다 실행 했을 때 코드가 끝나는건가? 싶었는데

갑자기  i가 1이 되고 반복문이 다시 실행이 되는거지? 였습니다.

즉, [ false, true , true, flase ] 처럼 이제는 인덱스 1의 값이 true로 고정이 된 상태에서 검사를 해주는 것이었습니다!

 

 

 

이해를 계속 못한 이유가

 

dfs 안에서 dfs를 호출하고 있음을 간과하고 있었습니다.

그리고 재귀의 정의를 간과하고 있었습니다.

 

재귀 함수의 호출 및 리턴 과정

 이미지 출처:  https://zorba78.github.io/cnu-r-programming-lecture-note/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98recursive-function.html 

 

 

재귀함수는

한번의 재귀가 끝나면 재귀 이전으로 돌아갑니다.

 

이 점을 상기 시킨 후 다시 예제로 돌아와보겠습니다.

처음에 main함수에서 dfs(0,0)을 호출합니다.

그래서 start 는 0이 됩니다.

아래의 백트래킹 함수에서 dfs(i+1,cnt+1)을 호출해서 dfs(1, 1)을 호출하게 됩니다.

이때의 이전 재귀함수의 start는 0입니다.

 

 

 

 

 

 

 

start가 1이고 cnt가 1이 되었는데 M이 2기때문에 다시 for문을 돌리게 됩니다.

 

 

 

 

 

 

 

 

 

start와 i가 1이고 cnt가 1인 상황에서 

DFS(i+1, cnt+1) 를 호출합니다.

 

이때 재귀가 끝나고 이전의 재귀로 돌아갔을 때 start의 값은 1이 되게 되는 것입니다!!

 

 

 

 

 

 

이런식으로 재귀가 끝나면 이전의 재귀로 return이 되기 때문에 모든 상황을 살필 수 있는 것이었습니다.

 

설명을 잘 했는지는 모르겠지만,, 

디버깅 영상도 첨부해볼테니 start값을 주시해서 봐주시면 감사하겠습니다!

 

 

이해가 되셨길 바라며,, 이만 물러나도록 하겠습니다!