[BOJ/Platinum 5] 백준 30975 약간 모자라지만 착한 친구야(C++)

문제 링크

https://www.acmicpc.net/problem/30975

 

 

문제

진주 나들이를 온 보선이는 경상국립대 정문 쪽 연못 산책길을 걷다가 울고 있는 동기 원우를 발견했다. 반가움보다 안쓰러움이 앞선 보선이는 원우한테 다가가서 울고 있는 이유를 물어봤다. 원우는 울면서 "교수님께서 경상국립대에서 출발해 경상국립대 주변에 있는 모든 동네에 가서 하늘 사진을 찍은 다음, 다시 경상국립대로 돌아오라는 심부름을 시키셨는데 거절을 못했어. 그런데 어떻게 심부름을 끝내야 할지 모르겠어."라고 대답했다. 약간 모자라지만 착한 원우를 위해 보선이가 대신 심부름을 맡기로 했다.

경상국립대 주변에 있는 동네는 총 N개이며, 각 동네는 1번부터 차례대로 번호가 부여되어 있다. 또한, 보선이는 편의상 경상국립대가 N + 1번이라 생각하기로 했다. 모든 동네는 한 번씩만 방문이 가능하며, 하늘 사진을 찍으러 출발하고 나서는 필요한 모든 하늘 사진을 찍기 전까지 경상국립대로 돌아올 수 없다. 그리고 경상국립대와 동네 N개 중 서로 다른 두 지점을 잇는 단방향 도로 M개가 있다. 시작 지점과 도착 지점이 모두 동일한 도로가 두 개 이상 존재할 수 있다.

추가적으로 교수님의 또 다른 부탁이자 당부가 있었다. 이는 임의의 두 하늘 사진의 시간적 차이가 필요함의 이유로, 어떤 동네의 하늘 사진은 그 동네에 정해진 다른 동네의 하늘 사진보다 늦게 찍어야 한다는 것이었다.

보선이는 성공적인 진주 나들이를 위해 심부름을 최대한 빠르게 마치기로 결심했다. 심부름을 마치는 데 걸리는 시간의 최솟값을 구해보자. 하늘 사진을 찍는 데 걸리는 시간은 무시하자.

 

입력

첫 번째 줄에는 경상국립대 주변에 있는 동네의 개수 N, 임의의 두 동네 사이를 잇는 단방향 도로의 개수 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 14; 1 ≤ M ≤ 200)

두 번째 줄에는 P1, …, PN이 공백으로 구분되어 주어진다. 이는 i번 동네의 하늘 사진은 Pi번 동네의 하늘 사진보다 늦게 찍어야 한다는 것을 의미한다. i = Pi인 경우에는 i번 동네에서 사진을 찍는 시점은 어느 때나 상관이 없다는 것을 의미한다. (1 ≤ Pi ≤ N)

세 번째 줄부터 M개의 줄에 걸쳐 각 단방향 도로의 정보 ui, vi, wi가 공백으로 구분되어 주어진다. 이는 i번째 도로는 시작 지점이 ui, 끝 지점이 vi번이며 도로를 지나는 데 걸리는 시간은 wi임을 의미한다. 1, …, N번 지점은 1, …, N번 동네를 뜻하며, N+1번 지점은 경상국립대를 뜻한다. (1 ≤ ui, vi ≤ N + 1; ui ≠ vi; 1 ≤ wi ≤ 100)

입력으로 주어지는 모든 수는 정수이다.

 

출력

첫 번째 줄에 심부름을 마치는 데 걸리는 시간의 최솟값을 출력한다. 만약 심부름을 마칠 수 없다면 –1을 출력한다.

 

예제 입력 1

2 6
2 2
3 1 1
1 2 1
2 3 1
3 2 2
2 1 2
1 3 2

예제 출력 1

6

예제 입력 2

2 6
2 1
3 1 1
1 2 1
2 3 1
3 2 2
2 1 2
1 3 2

예제 출력 2

-1

 

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

TSP를 이용하는데, i번째 동네를 방문하기 전 P[i]번째 동네를 방문했는지를 먼저 확인해야 한다.

P[i]번째 동네를 방문했다면 그 다음으로 i번째 동네를 방문해도 된다.

i와 P[i]가 같다면 그냥 i번째 동네를 방문해도 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 16
#define LL long long
#define INF 1e18
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, U, V;
LL W;
int P[MAX];
LL Dist[MAX][MAX];
LL DP[1 << MAX][MAX];
LL Answer = INF;

void init() {
	for (int i = 0; i < (1 << MAX); i++) {
		for (int j = 0; j < MAX; j++) {
			DP[i][j] = -1;
		}
	}
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			Dist[i][j] = INF;
		}
	}
}

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> P[i];
		P[i]--;
	}
	for (int i = 0; i < M; i++) {
		cin >> U >> V >> W;
		Dist[U - 1][V - 1] = min(Dist[U - 1][V - 1], W);
	}
}

LL getTsp(int Bitmask, int Now) {
	if (Bitmask == (1 << (N + 1)) - 1) {
		return (Dist[Now][N] == 0) ? INF : Dist[Now][N];
	}

	if (DP[Bitmask][Now] != -1) {
		return DP[Bitmask][Now];
	}

	LL MinDist = INF;

	for (int i = 0; i < N; i++) {
		if (Dist[Now][i] == INF) continue;
		int NowP = P[i];
		if (i == P[i]) {
			if ((Bitmask & (1 << i)) == 0) {
				LL NextDist = Dist[Now][i] + getTsp(Bitmask | (1 << i), i);
				MinDist = min(MinDist, NextDist);
			}
		}
		else if ((Bitmask & (1 << NowP)) != 0) {
			if ((Bitmask & (1 << i)) == 0) {
				LL NextDist = Dist[Now][i] + getTsp(Bitmask | (1 << i), i);
				MinDist = min(MinDist, NextDist);
			}
		}
	}
	
	return DP[Bitmask][Now] = MinDist;
}

void settings() {
	Answer = getTsp(1 << N, N);
}

void printAnswer() {
	if (Answer == INF) {
		cout << "-1\n";
	}
	else {
		cout << Answer << "\n";
	}
}

int main() {
    FASTIO

	init();
	input();
	settings();
	printAnswer();

    return 0;
}