/
/

BOJ : 백준 2098 외판원 순회(JAVA)

백준 2098 외판원 순회 풀이 기록 💡
알고리즘DP비트마스킹
avatar
vari
2025.04.29
·
9 min read

문제

시간 제한 : 1초, 메모리 제한 : 128MB
문제
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.
1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.
각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.
N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력
첫 줄에 N(도시의 수)
이후 N번만큼 각 도시로의 길이

출력
첫 줄에 외판원의 순회에 필요한 최소 비용 출력

풀이

DP로 풀면 될 것 같았는데 구현을 진심 어떻게 하면 좋을지 모르겠어서... 시간 제한도 너무 빡빡해서 당황했다.
결과적으로는 못 풀었고 타인의 풀이를 보고 이해했다. 아래는 이해한 내용을 기록해두기 위해 작성한다.

혼자 풀려고 할 때 생각해본 플로우는 재귀 함수를 사용하는 거였다. dp에 해당 도시로부터 출발하는 여행의 최소 비용을 저장해야겠다고 생각했다. 근데 그러면 따로 어느 도시를 들렀는지를 함께 기록해둬야 했고, 순열과 비슷하다고 생각해 구현해볼까 했으나 시간 제한 때문에...🥺

어쨌든 사용해야 하는 방법들은 DP, 비트마스킹이다.
비트마스킹이라는 방법을 이번에 처음 알게 됐는데, 별 거 없다. 첫 번째 도시를 방문 했으면 2^0비트 자릿수를 1로 바꾼다. 두 번째 도시를 방문했으면 2^1비트 자릿수를 1로 변경, 이렇게 비트마스크를 사용하여 방문한 곳들을 기록해두는 것이다.

문제 풀기 전 알아둬야 하는 사항들은 이렇다.
1. 시작 지점을 고정시켜도 된다.

1 > 2 > 3 > 4
2 > 3 > 4 > 1
3 > 4 > 1 > 2
4 > 1 > 2 > 3

이 네 경로는 시작점은 달라도 모두 동일한 경로이기 때문에, 시작하는 도시를 하나만 잡아도 모든 경우의 수를 커버할 수 있다.

  1. 중복되는 연산이 존재한다.

    1 > 2 > 3 > 4
    2 > 1 > 3 > 4

이렇게 뒷 부분, 3 > 4 부분이 겹친다. 이 중복 연산 문제는 DP를 통해 해결할 수 있다.

dp[현재 도시][비트마스크]

현재 도시~비트마스크에 표시가 안 된 도시를 모두 방문한 후 돌아갈 때까지 드는 최소 비용

1 << i

i번째 비트만 1로 변경하는 비트마스크 (왼쪽으로 shift)

route와 dp array를 선언하고, dp array는 -1로 초기화해준다.
tsp 메소드로 0번째 도시에서의 최소 비용을 구한다.

tsp 메소드는 현재 도시의 위치와 비트마스크를 매개변수로 받는다.

비트마스크를 확인했는데 모든 도시를 방문했다면
현재 도시로부터 0번째(시작) 도시로 가는 길 길이를 반환한다. 만약 현재 도시로부터 시작 도시까지 가는 길이 0이면 INF를 반환한다.
(Integer.MAX_VALUE 대신 INF를 사용한다. 더해야하는데 Integer.MAX_VALUE가 잘못 들어오면 오버플로우로 인해 -2.... 거대한 숫자가 나올 수 있기 때문이다.)

값이 -1가 아니라면
이미 계산된 값이므로 현재 값을 반환한다.

값이 -1이면
INF로 초기화 후, for문으로 0~N까지 돌린다.
비트마스킹을 확인해 해당되는 값(i)가 방문하지 않은 도시일 때고, 현재 도시로부터 갈 수 없는 도시가 아니라면
dp[currentCity][visitBitmask]와 tsp(i, 비트마스크 | (1 << i)) + routes[현재 도시][i]를 비교한다.

-1로 초기화 했다가 INF로 초기화하는 이유는 경로가 없는 경우에도 INF를 return 하기 때문에, 방문하지 않은 상태와 경로가 없는 상태를 구분하기 위해서이다.

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int[][] routes;
	static int[][] dp;
	
	static final int INF = 16_000_001;
	
	static int tsp(int currentCity, int visitBitmask) {
		if(visitBitmask == (1 << N) - 1) {
			if(routes[currentCity][0] == 0) {
				return INF;
			}
			
			return routes[currentCity][0];
		}
		
		if(dp[currentCity][visitBitmask] != -1) {
			return dp[currentCity][visitBitmask];
		}
		
		dp[currentCity][visitBitmask] = INF;
		for(int i = 0; i<N; i++) {
			if((visitBitmask & (1 << i)) == 0 // i번째 도시 방문 여부 체크
					&& routes[currentCity][i] != 0) { // 현 도시 -> i번째 도시 갈 수 있는지 확인
				dp[currentCity][visitBitmask] = Math.min(dp[currentCity][visitBitmask],
						tsp(i, visitBitmask | (1 << i)) + routes[currentCity][i]); // 현재 dp와 i번째 도시를 방문한 것으로 업데이트한 tsp와 비교
			}
		}
		return dp[currentCity][visitBitmask];
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		routes = new int[N][N];
		dp = new int[N][(1 << N)];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for(int j=0; j<N; j++) {
				routes[i][j] = Integer.parseInt(st.nextToken());
			}
			Arrays.fill(dp[i], -1);
		}
		
		bw.write(String.valueOf(tsp(0, 1)));
		bw.flush();
		bw.close();
		br.close();

	}

}

문제를 풀며

정말 너무 어려웠다 그래도 이해하니 뿌듯하다! 🥹

풀이를 위해 참고한 withhamit님의 글
풀이를 위해 참고한 zeesouth님의 글

- 컬렉션 아티클