[BOJ/Silver 2] 백준 31871 영일랜드(C++)

문제 링크

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

 

문제

영일랜드는 하나의 정문과 N개의 놀이기구로 이루어진 테마파크로 각각 식별 번호가 매겨져 있다. 정문은 0번, 놀이기구는 1번부터 N번까지의 번호로 구분된다. 정문과 놀이기구 혹은 놀이기구와 놀이기구 사이에는 단방향 간선으로 이어진다. 두 장소를 잇는 간선은 여러 개일 수 있으며 출발 장소와 도착 장소가 같을 수도 있다.

영일랜드에 놀러 간 정민이는 영일랜드의 정문에서 출발해 모든 놀이기구를 한 번씩만 탑승하고 정문으로 돌아오는 경로의 최장 시간이 궁금하다. 영일랜드의 놀이기구는 매혹적이어서 안 타고 지나갈 수 없어 각 놀이기구에는 최대 한 번씩만 도달할 수 있다. 또한, 모든 놀이기구를 탑승할 때까지 정문을 경유할 수 없으며 놀이기구 탑승 시간은 무시한다.

호기심이 많은 정민이를 위해 최장 시간을 알려주자.

 

입력

첫 번째 줄에는 놀이기구의 개수 N이 주어진다. (1 ≤ N ≤ 9)

두 번째 줄에는 간선의 개수 M이 주어진다. (0 ≤ M ≤ 10,000)

다음 M개의 줄에는 정문 또는 놀이기구의 식별 번호 ui에서 vi로 향하는 간선의 이동 시간인 정수 di가 공백을 사이에 두고 차례로 주어진다. 간선의 이동 시간의 합은 2^31보다 작다. (0 ≤ ui, vi ≤ N; 1 ≤ di ≤ 2^(31−1))

 

출력

정민이가 정문에서 출발해 모든 놀이기구를 한 번씩 탑승하고 다시 정문으로 돌아오는 경로의 최장 시간을 출력한다. 만약 불가능하다면 -1을 출력한다.

 

예제 입력 1

2
8
0 1 18
0 2 20
0 2 15
1 0 10
1 2 15
2 0 13
2 2 10
2 1 5

예제 출력 1

46

예제 입력 2

2
4
0 1 18
0 2 20
1 0 10
1 2 15

예제 출력 2

-1

 

알고리즘 분류

• 백트래킹

 

풀이

모든 놀이기구는 방문하면 반드시 탑승을 해야 하고, 모든 놀이기구를 한 번씩만 탑승하고 다시 정문으로 돌아와야 하므로, N번째 놀이기구에 탑승한 후 바로 정문으로 돌아오는 경로가 존재해야 한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 10
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, U, V, D;
int MAP[MAX][MAX];
bool Visited[MAX];
int Answer = -1;

void input() {
    cin >> N;
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> U >> V >> D;
		if (U == V) continue;
		MAP[U][V] = max(MAP[U][V], D);
    }
}

void dfs(int Now, int Sum, int Count) {
    if ((Now == 0) && (Count == N + 1)) {
        Answer = max(Answer, Sum);
		return;
    }

	for (int i = 0; i <= N; i++) {
		if (MAP[Now][i] == 0) continue;
		if (!Visited[i]) {
			Visited[i] = true;
			dfs(i, Sum + MAP[Now][i], Count + 1);
			Visited[i] = false;
		}
	}
}

void settings() {
    dfs(0, 0, 0);
}

void printAnswer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    printAnswer();

    return 0;
}