[java] 백준(BOJ) - 외판원 순회

문제

백준-외판원 순회
한 도시에서 출발해 N개의 도시를 모두 거친 후 출발지로 돌아오는 경로 중 최소비용을 구하는 문제

• 제한 사항
  도시의 수 N : 2 <= N <= 16
  도시 i에서 j로 가는 비용 W[i][j] : W[i][j] <= 1,000,000(비용은 대칭적이지 않음)
  도시 i에서 j로 갈 수 없는 경우 W[i][j] = 0

풀이

비트마스킹에 대해 포스트를 작성했으니 적용 문제를 풀어보기로 했다
우선 1 ~ N번까지의 도시가 있는데 0번부터 N-1까지로 코드를 작성했다
이동 경로를 기록하기 위해 memo배열을 선언했고 크기는 memo[N][1 << N]이다

열의 크기가 1 « N 인 이유는, 예를들어 N = 3이라고 할 때
도시 3개의 부분집합은 (각 도시를 A,B,C라고 한다면)
0(없음), A, B, C, AB, AC, BC, ABC 이렇게 총 8개가 된다
1 « 3을 하면 1을 3번 왼쪽으로 밀고 빈 자리는 0이 채우게 되므로 이진수 1000, 십진수로 8이 된다

위의 부분집합은 방문한 도시를 의미한다
도시를 A,B,C라고 하고 101이 방문한 값이라고 한다면
비트 | 도시 | 방문여부
1 | A | (방문했음)
0 | B | (방문 X)
1 | C | (방문했음)
같이 의미하게 된다

tsp(현재 도시, 방문 상태) 이렇게 재귀식으로 함수가 도는데
curr은 현재도시, state는 방문상태를 의미한다

int min = inf;
for (int i = 0; i < N; i++) {
			if (map[curr][i] > 0 && (state & (1 << i)) == 0) {
				min = Math.min(min, tsp(i, (state | (1 << i))) + map[curr][i]);
			}
		}

map[curr][i] > 0으로 curr과 i(다음 도시)가 연결되어있는지 확인한다
(state & (1 << i)) == 0으로 state의 i번째 원소가 1인지 0인지 판별한다
1인 경우 0보다 큰 값이 나오고, 0인 경우 0이 나온다

현재 도시에서 방문하지 않은 도시들을 순회하면서 최소비용을 갱신한다
tsp(i, (state | (1 << i))) + map[curr][i]);는
첫번째 매개변수 i는 다음에 갈 도시
두번째 매개변수는 i번째 도시를 방문하기로 했으므로 1 « i한 값을 state에 더해준다
즉, state의 i번째 비트를 1로 바꿔준다
리턴된 값에 curr에서 i로 가는 비용을 더해서 최솟값을 구한다

그 외 이미 저장된 값이 있거나, 전체를 순환한 경우 0으로 가는 비용이 없는 경우 등등
비트마스킹보다는 dp, 백트래킹 같은 느낌이라 설명은 생략한다

시행착오

1) 갈 수 없음을 memo배열에 저장할 때 Integer.MAX_VALUE를 사용함
min을 갱신할 때 [tsp(다음도시) + 현재도시와 다음도시 이동비용]을 계산하는데
만일 tsp의 리턴값이 Integer.MAX_VALUE면, 덧셈을 할 때 int범위를 넘어서서 음수값이 나오므로
제대로된 계산을 하지 못한다 ㅠㅠ

2) 처음 문제를 이해할 때 시작점에 대한 의문
도시가 3개가 있다면 처음 시작도시에서 출발해서 다시 처음으로 되돌아오는 경우를 제외한다면

1번부터 시작하는 경로 : 1 - 2 - 3 - 1
2번부터 시작하는 경로 : 2 - 3 - 1 - 2
3번부터 시작하는 경로 : 3 - 1 - 2 - 3
원순열과 같은 형태이므로 다 같은 경로라고 볼 수 있다
그래서 0번 도시에서 출발해도 같은 결과를 가져온다

소스코드

// 패키지 생략

public class Main {

	private static int N;
	static int[][] map;
	static int memo[][];
	static final int inf = 987654321; // 최댓값

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		memo = new int[N][1 << N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		System.out.println(tsp(0, 1));
	}

	private static int tsp(int curr, int state) {
		if (state == (1 << N) - 1) { // 모든 도시를 방문 했을 경우  
			if (map[curr][0] > 0) // 0에서 시작했으므로 0으로 가는 경로가 존재하면
				return map[curr][0]; // 마지막 비용을 돌려줌
			else
				return inf; // 없는 경우 -> 불가능
		}

		if (memo[curr][state] > 0) // 이전에 기록이 남아있다면
			return memo[curr][state]; // 기록내용 돌려줌

		int min = inf; // 최솟값을 찾아보자
		for (int i = 0; i < N; i++) {
			if (map[curr][i] > 0 && (state & (1 << i)) == 0) { // 현재도시 (curr)에서 다른 도시(i)로 갈 수 있고, 방문 안했다면
				min = Math.min(min, tsp(i, (state | (1 << i))) + map[curr][i]); // 값 갱신
			}
		}
		return memo[curr][state] = min; // 최솟값을 저장하고 리턴
	}
}