문제
이번 문제는 외판원 순회 문제
Traveling Salesman problem (TSP)라고 불리는 문제로 computer science에서 중요한 문제랍니다
1번부터 N번까지의 도시가 있는데 모든 도시를 방문하고 처음에 출발했던 도시로 다시 돌아가면 된다
이미 방문했던 도시는 다시 방문해서는 안 된다
한 도시에서 다음 도시로 이동하는 비용은 W라는 2차원 배열을 통해서 주어진다
W[i][j]는 i라는 도시에서 j라는 도시까지 이동하는 비용을 이미
W[i][i]는 이동하지 않는 것이므로 0이라고 생각한다
만약 도시 i에서 j로 이동할 수 있는 경로가 없을 경우에도 0이다
비용은 대칭적이지 않다!! 즉, W[i][j]와 W[j][i]는 다를 수 있다는 것
문제가 우리에게 원하는 것은 가장 적은 비용으로 모든 도시를 도는 방법이다
알고리즘
생각해야 할 것은 모든 도시를 돌아야 한다는 것
그래서 그리디 알고리즘은 안 되겠다..
지금 당장의 최선의 선택이 최소의 비용을 만드는 것이 아니기 때문
또한 무조건 처음으로 다시 돌아와야 하는데 이는 적합한 알고리즘이 아니겠다는 판단이 들었다
문제에서 출발점을 주지 않았다는 것도 고려해야 한다
하지만 이는 중요치 않은데 처음으로 돌아온다는 것은 출발을 어디서 하던 모든 길을 다 방문하기 때문에 출발점은 내가 임의로 잡아도 된다
이게 무슨 소리냐면
1 -(3)-> 2
2 -(2)-> 3
3 -(5)-> 1
라고 가정해보자
1에서 시작해 2와 3을 거쳐 다시 1로 돌아오면 2 + 3 + 1 = 6
2에서 시작해서 3과 1을 거쳐 다시 2로 돌아오면 3 + 1 + 2 = 6
3에서 시작해서 1과 2를 거쳐 다시 3으로 돌아오면 1 + 2 + 3 = 6
모두 같은 값을 가지는 것을 알 수 있다
자 이제 정해야 하는 것은 어떤 탐색 알고리즘을 사용하냐는 것이다
앞에서 설명했듯이 그리디는 안 되고..
"순회"한다는 것을 이용해서 DFS를 사용하기로!
내가 방문했는지 안했는지 확인하는 배열이 필요하겠다
Math 이용해서 최솟값 찾고..
그럼 코드로 가볼까요?
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Baekjoon10971 {
static int N;
static int W[][];
static int min = Integer.MAX_VALUE;
static boolean[] visited;
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
W = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
W[i][j] = Integer.parseInt(st.nextToken());
}
}
visited = new boolean[N];
Arrays.fill(visited, false);
visited[0] = true;
dfs(0, 0);
System.out.println(min);
}
// 탐색 알고리즘
public static void dfs(int now, int cost) {
// 만약 모든 도시를 방문했다면 안의 명령문 실행
if (allvisited() == true) {
// 마지막 방문 도시에서 처음 도시로 돌아갈 방법이 있다면 최솟값 구하는 것으로 마무리 (다른 경로들 중 가장 작은 값이 min)
// cost + W[now][0]는 이전 경로의 비용에 현재 돌아가는 비용을 더하는 연산
if (W[now][0] != 0)
min = Math.min(cost + W[now][0], min);
return;
}
// 도시를 모두 도는데 필요한 for문
for (int i=1 ; i<N ; i++) {
// i 도시를 방문하지 않았고 현재 있는 곳에서 i 도시를 방문할 길이 있다면 계속 탐색 진행
if (visited[i] == false && W[now][i] != 0) {
visited[i] = true;
dfs(i, cost + W[now][i]);
// 혹시 다음 도시에 갈 방법이 없다면 방문하지 않았음을 표시
visited[i] = false;
}
}
}
// 모든 도시를 다 돌았는지 확인하는 함수
public static boolean allvisited() {
for (int i=0 ; i<N ; i++) {
if (visited[i] == false) return false;
}
return true;
}
}
마무리
호기롭게 시작했던 것과 달리.. 생각보다 생각해야 될 것들이 많다
아무래도 dynamic programming은 내가 못하던 재귀함수의 개념이 포함되어 있어서 조금 어렵다
처음에는 3개의 도시만 있다고 생각하고 코드를 한 줄 씩 짜보니 그나마 감을 잡을 수 있었다
앞으로도 동적프로그래밍.. 아자아자 화이팅
