[BOJ] 외판원순회2 / Java / 백트래킹

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

 

 

풀이방법

 

백트래킹 사용 ( 정점을 지나는 경우의 수를 찾고, 아닌 경우 다시 돌아간다.) 

 

1. 모든 정점을 다 지나야 하는 모든 경우의 수를 구하기.

•  이 때, W[i][j] = 0 인 경우 이동할 수 없음. 

2. 모든 정점을 다 지난 후, 최솟값을 구하고 비교하기.

•   모든 정점을 다 지난 후 제일 첫번째로 돌아와야함 ( 마찬가지로, W[i][j]= 0인 경우 이동할 수 없음.

 

 

 

* 백트래킹 이란?

백트래킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지(유망하지 않은지) 판단하고 그러한 경우 해당 상태(노드)를 제외하고 다음 단계로 나아가는 방식이다.

여기서 알아둘 것은 특정 상태(노드)를 제외한다는 것이다.

 

즉, 이 방법을 통해 우리는 모든 경우의 수를 체크 하지 않고 필요한 것만 체크하여 전체 풀이 시간을 단축할 수 있게 된다!

 

백트래킹을 사용하는 알고리즘 중 하나는 대표적으로 DFS가 있다. DFS는 재귀를 통해 가능한 경로 중 유망한 경로만 찾아서 탐색을 수행한 뒤 다시 돌아와 그 중 가장 최적의 경로를 반환한다.

 

백트래킹을 사용해 해결할 수 있는 문제는 의사 결정, 최적화, 열거하기 등의 경우가 있다.

사실 백트래킹은 사용 가능한 경우가 많지만 시간복잡도가 보통 Exponential(지수, 2n2n 꼴)이며, 대부분 Dynamic Programming, 그리디 알고리즘 등으로 더 빠르게 해결할 수 있다.

하지만 일부 경우의 문제들은 여전히 백트래킹으로만 해결이 가능한 문제도 있으며 그러한 경우에 많이 사용된다.

 

 

* 참고) DFS와 백트래킹(Backtracking)의 차이

DFS는 기본적으로 그래프 형태 자료구조에서 모든 정점을 탐색할 수 있는 알고리즘 중 하나이다. 깊이를 우선적으로 탐색하기에 재귀 또는 스택을 이용한다. 재귀를 이용하여 탐색을 수행한다는 부분에서 완전탐색 알고리즘의 재귀 / 백트래킹(Backtracking)과 유사한 측면이 보여 혼란이 올 수 있다.

그런데, 재귀라는 것은 말 그대로 스스로의 함수(또는 메소드)를 호출하는 방식을 의미하는 것이므로 DFS가 재귀라는 방식을 이용해 탐색을 수행하는 것으로 하나의 방식이라고 이해하면 된다.

또한 백트래킹(Backtracking)은 재귀를 통해 알고리즘을 풀어 가는 기법 중 하나로 가지치기(Pruning)을 통해서 탐색을 시도하다가 유망하지 않으면 추가 탐색을 하지 않고 다른 해를 찾는 방법이다.

DFS는 기본적으로 모든 노드를 탐색하는 것이 목적이지만 ,상황에 따라서 백트래킹 기법을 혼용하여 불 필요한 탐색을 그만두는 것이 가능하다.

 

DFS와 백트래킹은 모두 재귀호출을 통해 알고리즘을 풀어가는 기법이라는 점이 비슷하지만,

DFS는 모든 정점을 탐색하는 알고리즘이고,

백트래킹은 가지치기(Pruning)을 통해서 탐색을 하다가 다시 돌아가서 최적의 방법을 탐색하는 알고리즘이다.