접근
외판원 순회 문제는 백준의 2098번 외판원 순회 문제와 1029번 그림교환 문제를 통해서 배우게 되었다.
외판원 순회 문제는 한번 들린 곳은 다시 들리지 않으며 모든 곳을 다 순회하고 마지막에 자기 자신으로 돌아오는 사이클이 존재한다. 여러개의 사이클 중에서 각 간선마다 가중치가 있다고 가정할 때 최소의 비용이 드는 사이클을 발견하는 것이 이 문제의 목적이다.
처음에 이 문제를 BFS를 통해서 해결하고자 했다.
하나의 내부 클래스를 만들어서 그 객체를 Queue에 적재하고자 했다. 하지만 메모리 초과가 발생했다.
static class Ex{
int artist;
int cost;
boolean[] check;
public Ex(int artist, int cost, boolean[] check){
this.artist = artist;
this.cost =cost;
this.check=check;
}
}왜냐하면 내부 클래스에 visit 상태 배열을 넣어서 각 Queue마다 한번 간 곳과 가지 않은 곳을 표시했기 때문이다.
이 문제는 뭔가 서로 공유할 수 있는 상태 배열이 필요하다고 느꼈고 결국 다른 사람의 풀이를 통해서 "외판원 순회 문제"라는 유형을 알게 되었다.
과정
외판원 순회 문제는 세가지 알고리즘을 이용한다.
비트마스킹, DP, DFS이다.
💡여기서 비트마스킹은 내가 직면했던 서로 공유하는 상태 배열에 대한 문제를 해결해준다.
만약에 도시가 5개 있다고 한다면
1번 도시를 방문했다면 00001
2번 도시는 00010
1번과 2번도시는 00011
오른쪽부터 방문 도시를 1로 방문하지 않은 도시를 0으로 표현한다.
따라서 AND 연산을 통해서 두개의 비트 연산자를 했을 때 0이 나온다면 방문하지 않은 도시를 나타낸다.
예를 들어 01110를 통해 방문한 도시를 표시
그리고 방문하고자 하는 도시를 00001이라면
01110 & 00001 의 결과는 0이다!
또한 OR 연산자를 통해서 여태까지 방문했던 도시 01110과 지금 방문한 도시 00001에 대해서 방문한 도시에 대한 기록을 갱신해준다.
01110 | 00001 의 결과는 011111이다!
💡 DP는 DFS의 횟수를 줄여준다.
외판원 문제는 사이클이며
최소비용을 구하는 문제라고 했다.
일단 이 부분을 이해하려면 DFS와 같이 말해야한다.
DFS의 경우 재귀함수를 호출하는 방식으로 진행되는 깊이 우선 탐색인데
1번 도시에서 순회를 시작한다. 코드는 단순화해서 아래와 같다고 가정하자.
static void main(String[] args) {
DFS(1,1);
}
static void DFS(int i, int state){
if(state == 모든 도시를 방문한 상태의 10진수값 ){
return 마지막 도시가 1번 도시를 가는데 드는 비용
}else{
for(int a: 1과 연결된 도시들){
DFS (a);
}
}
}대충 위와 같다고 가정할 때
DFS는 이렇게 갈 것이다.
1->2->3->4->5
그다음 DFS는 1->3->2->4->5으로 갈 때
우리가 볼 부분은 겹치는 부분이다.
1->2->3으로 가는 최소 경로 비용이나
1->3->2로 가는 최소 경로 비용은 같을 것이다.
이미 전 DFS로 저장된 최적의 경로를 다시 이용하겠다는 것이다. DP가 이용된다.
자바코드
위에 제시된 백준의 외판원 순회 문제에 대한 풀이로 대신한다.
import java.io.*;
import java.util.*;
public class Main{
static int[][] city;
static int[][] dp;
static int INF= 987654321;
static int N;//도시 수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());// 도시 개수 2~16개
city = new int[N][N];
dp = new int[N][(1<<N)-1];
for(int[] v : dp){
Arrays.fill(v,-1);
}
StringTokenizer st = null;
for(int i=0;i<N;i++){
st =new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++){
int c = Integer.parseInt(st.nextToken());
city[i][j]=c;
}
}
int answer = dfs(0,1);
// 처음도시는 아무곳이나 상관 없지만 0번 도시붙터 탐색
//state 00001(도시 5개라면)
bw.write(Integer.toString(answer));
bw.flush();
bw.close();
br.close();
}
static int dfs(int start_c , int state){
if(state== (1<<N)-1){
// 0번 도시로 돌아갈 수 없는 경우
if(city[start_c][0]==0) return INF;
// 0번 도시로 돌아갈 수 있는 경우
else return city[start_c][0];
}else {
// 이미 도시를 방문한 경우, 이미 state에 대한 정보를 다 가지고 있는 경우 1->3->4 이후 1->4->3이 들어온 경우
if (dp[start_c][state] != -1) return dp[start_c][state];
//---------------------------------------------------
//출석 표시
dp[start_c][state] = INF;
for (int i = 0; i < N; i++) {
//방문한 도시에 대한 상태를 바꿔준다.
int next = state | (1 << i);
// 도시를 갈 길이 없거나 이미 도시를 방문한 경우
// (도시를 방문했으면 같은 자리에 1이 있으므로 1 이상의 값이 무조건 나옴)
if (city[start_c][i] == 0 || (state & (1 << i)) != 0) continue;
dp[start_c][state] = Math.min(dp[start_c][state], dfs(i, next) + city[start_c][i]);
}
return dp[start_c][state];
}
}
}