BOJ 2098번: 외판원 순회

문제

문제 바로가기> BOJ 2098번: 외판원 순회

2098번: 외판원 순회

 

풀이

중요한 Point 

 

1. 출발지가 어디든 그 결과는 같다.

A → B → C → A

B → C → A → B

C → A → B → C 

 

조금만 들여다보면,

순회하기 때문에, 어느 지점에서 출발하든 동일한 경로가 되는 것을 확인할 수 있다.

따라서 출발지를 고정 시킨 후 탐색을 진행한다!

 

2. 중복되는 경로가 생긴다.

이미 방문해서 최소값을 찾아 놓은 부분 경로의 경우, 또 다시 연산을 진행할 필요가 없다.

`dp[now][visit]` : visit에서 방문하지 않은 도시를 각각 한번 씩 거쳐서 출발지로 도착하는 최단 경로

 

++ Java의 경우, Arrays.fill()을 이용해 INF로 초기화를 했을 때, 시간 초과가 발생했음 ㅎ

 

C++

#include<iostream>
#include<cstring>
#define MAX 16
#define INF 1000000001
using namespace std;

int N, END;
int cost[MAX][MAX];
int dp[MAX][1<<MAX];

void input(){
    cin >> N;
    END = (1<<N)-1;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) cin >> cost[i][j];
    }
}

int solution(int now, int visit){ // 외판원의 순회에 필요한 최소 비용
    if(visit == END){ // 모두 방문한 경우
        if(cost[now][0]==0) return INF; 
        return cost[now][0]; // 출발지로 돌아갈 수 있다면
    }

    int &res = dp[now][visit]; // 이미 값을 저장해둔 경우
    if(res!=-1) return res; res = INF;
    for(int next=0; next<N; next++){
        if(cost[now][next]==0 || visit&(1<<next)) continue; // 경로가 없거나, 이미 방문한 경우
        res = min(res, cost[now][next]+solution(next, visit|(1<<next)));
    }
    return res;
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    memset(dp, -1, sizeof(dp)); // init
    cout << solution(0, 1); // 0번 출발지에서 시작 (어디서 시작하든 결과는 같음)
}

 

Java

package solution;

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

public class Main {
	
	static final int INF = 1000000000;
	
	static int N;
	static int[][] cost, dp;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		cost = new int[N][N];
		dp = new int[N][1<<N];

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

	private static int solution(int now, int visit) {
		if(visit == (1<<N)-1) {
			if(cost[now][0] == 0) return INF;
			return cost[now][0];
		}
		
		if(dp[now][visit]!=0) return dp[now][visit];
		
		dp[now][visit] = INF;
		for(int next=0; next<N; next++) {
			if(cost[now][next]==0 || (visit&(1<<next))!=0) continue;
			 dp[now][visit] = Math.min(dp[now][visit], cost[now][next]+solution(next, visit|(1<<next)));
		}
		
		return dp[now][visit];
	}
}