이번 문제는 백준 실버 2 문제인 외판원 순회 2 문제이다.
TSP(Traveling Salesman Problem) 문제는 꽤 유명한 알고리즘 문제이다.
이번 기회에 혼자서 생각하며 한 번 풀어보자.
먼저 문제부터 차근차근 읽어보자.
도시의 수와, 비용 행렬이 주어지며 최소 비용으로 모든 도시를 순회해야 한다.
나는 이런 그래프 탐색 문제에서는 그래프의 자료구조를 가장 먼저 생각해본다.
인접 행렬, 인접 리스트 등 다양하게 그래프를 표현할 수 있는데,
문제에 따라 사용되는 그래프의 구조가 다르기 때문에 고민을 해보아야 한다.
어? 그런데 이 문제에서는 이미 행렬 형태로 입력을 주었다.
그럼 우선 인접 행렬 형태로 비용을 한 번 받고 사용해보자.
이제 외판원을 움직일 차례다.
어떤 식으로 풀어야 시간 초과가 나지 않고 최소 비용을 구할 수 있을까?
먼저, 최단 경로를 찾는 알고리즘으로 다익스트라 를 생각해볼 수 있다.
하지만, 다익스트라는 특정 출발지에서의 최단 경로를 구하는 알고리즘이다.
즉 모든 경로를 탐색하는 이번 문제에는 어울리지 않는다.
백트래킹
그럼 직접 모든 경로를 다 탐색해서 최소 비용의 경로를 찾아내는 방식은 어떨까?
도시의 수가 10개 밖에 되지 않기 때문에 가능성이 있어보인다.
또한 더욱 빠른 연산을 위해서 최소 비용을 갱신하며,
갱신된 비용보다 커지는 경로는 진행하지 않도록 pruning 한다.
또한, 이미 방문한 지점을 다시 방문할 수는 없기 때문에 체크를 해주어야 한다.
이런 방식으로 푸는 문제를 우리는 Backtracking 이라고 한다.
잠깐, 이미 방문한 지점을 다시 방문하지 못한다면 출발지는 어떻게 하지?
모든 도시를 돌았을 때, 마지막 도착한 도시에서 출발지로 이어주면 되지 않을까?
if (depth == num) {
if (graph[idx][start_pos] != 0) {
// 출발지로 갈 수 있는 길이 있다면? 연결
cost += graph[idx][start_pos];
answer = min(answer, cost);
cost -= graph[idx][start_pos];
}
return;
}위의 코드와 같이 추가적인 비용을 결과에 더해주고, 다시 빼고 마저 탐색한다면?
이대로 구현한 뒤 한 번 제출해보자.
운이 좋게도 백트래킹이 정답이었다.
중요 로직의 구현 코드는 아래와 같다.
void backtrack(int start_pos, int idx, int depth, int cost) {
if (depth == num) {
if (graph[idx][start_pos] != 0) {
cost += graph[idx][start_pos];
answer = min(answer, cost);
cost -= graph[idx][start_pos];
}
return;
}
if (cost > answer)
return;
for (int i = 0; i < num; i++) {
if (!visit[i] && graph[idx][i] != 0) {
visit[i] = true;
backtrack(start_pos, i, depth + 1, cost + graph[idx][i]);
visit[i] = false;
}
}
}
int main(){
for (int i = 0; i < num; i++) {
visit[i] = true;
backtrack(i, i, 1, 0);
// 모든 출발지를 다 돌도록 설정한다.
visit[i] = false;
}
}가장 일반적인 형태의 TSP 문제를 풀어보았다.
처음엔 플로이드 와샬 의 형태로도 문제를 풀 수 있지 않을까?
하는 생각이 들었는데, 불가능 하다는 생각이 바로 들었다.
플로이드 와샬은 모든 도시를 순회한다는 보장이 없기 때문이다.
다익스트라도 못쓰는 상황에서 내가 생각 할 수 있는 것은 완전 탐색 뿐이었다.