hwooo
BOJ (Java) 2098번: 외판원 순회 본문
https://www.acmicpc.net/problem/2098
풀이
완전 탐색의 방법으로 시도하려 했으나, 이 경우 탐색해야 할 노드의 수가 많아져 시간 초과가 발생한다.
알고리즘을 보니 비트마스킹과 DP가 있어 바로 풀이를 봤다.
유명한 알고리즘이었으나 접근 방법이 생소해서 모르면 못 풀겠다 싶었다.
[알고리즘] 외판원 순회 문제
모든 도시들을 단 한번씩만 방문하고 원래 시작점으로 돌아오는 최소 비용을 구해보자!
velog.io
Java 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static final int INF = 16_000_000;
private static int N;
private static int end;
private static int[][] money;
private static int[][] dp;
public static void main(String[] args) throws IOException {
// input
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bf.readLine());
money = new int[N][N];
dp = new int[N][1 << N]; // N 개의 도시를 비트 마스킹으로 표시하기 위해
end = (1 << N) - 1;
// 도시 간 거리 입력 저장
for (int i = 0; i < N; i++) {
String[] inputs = bf.readLine().split(" ");
for (int j = 0; j < N; j++) {
money[i][j] = Integer.parseInt(inputs[j]);
}
}
System.out.println(tsp(0, 1));
}
private static int tsp(int now, int visited) {
// 모든 도시를 다 돌았을 때
if (visited == end) {
// 현재 노드 (마지막에 방문한)에서 시작점을 갈 수 있다면 해당 값 반환
if (money[now][0] > 0) {
return money[now][0];
}
return INF;
}
// 방문했다면 저장한 값 반환, 아니라면 INF로 초기화 (최솟값 비교를 위해)
if (dp[now][visited] != 0) {
return dp[now][visited];
} else {
dp[now][visited] = INF;
}
// 갈 수 있는 모든 노드를 탐색, 최솟값을 찾음
for (int i = 0; i < N; i++) {
if (money[now][i] == 0) continue;
if ((visited & (1 << i)) != 0) continue;
int tmp = tsp(i, visited | 1 << i);
dp[now][visited] = Math.min(dp[now][visited], money[now][i] + tmp);
}
return dp[now][visited];
}
}
'Study > Algorithm' 카테고리의 다른 글
프로그래머스 (Java) 258707 : n + 1 카드게임 (0) | 2025.05.25 |
---|---|
BOJ (Java) 16236번: 아기 상어 (0) | 2025.05.25 |
프로그래머스 (Java) 140285 : 디펜스 게임 (0) | 2025.05.19 |
BOJ (Java) 9466번: 텀 프로젝트 (0) | 2025.05.17 |
BOJ (Java) 9252번: LCS2 (0) | 2025.05.16 |