[BOJ/Gold 4] 백준 12875 칙령(C++)

문제 링크

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

12875번: 칙령

 

문제

총 N명의 사람이 살고있는 왕국이 있다. 각 사람이 가지고 있는 돈은 음이 아닌 정수이다.

사람들은 1번부터 N번까지 번호가 매겨져 있다.

어느 날. 왕이. 다음과. 같은. 칙령을. 선포했다.

모든 사람이 가지고 있는 돈은 자신의 친구가 가지고 있는 돈과 최대 d원 만큼 차이가 나야 한다.

즉, 어떤 사람이 가지고 있는 돈이 x가 되려면, 친구 중에 x-d보다 작거나, x+d보다 큰 돈을 가진 사람이 없어야 한다.

사람들은 가능한 돈의 분배 방법 중에서 돈을 가장 많이 가진 사람과 적게 가진 사람의 차이가 가장 크게 되도록 분배하려고 한다.

사람의 수와 친구 관계가 주어졌을 때, 왕의 칙령을 지켜 돈을 분배하는 방법을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (2 ≤ N ≤ 50)이 주어진다. 

둘째 줄에는 d (0 ≤ d ≤ 1,000)가 주어진다.

셋째 줄부터 N개의 줄에는 사람들의 친구 관계가 주어진다. i번째 줄의 j번째 문자가 Y인 경우에는 i번 사람과 j번 사람이 친구라는 뜻이고, N인 경우는 친구가 아니라는 뜻이다. 항상 i번째 줄의 i번째 문자는 N이며, i번째 줄의 j번째 글자와 j번째 줄의 i번째 글자는 같다.

출력

첫째 줄에 가능한 돈의 분배 방법 중에서 돈을 가장 많이 가진 사람과 적게 가진 사람의 차이가 최대가 될 때의 최댓값을 출력한다. 이 차이가 무한대인 경우에는 -1을 출력한다.

예제 입력 1

3
10
NYN
YNY
NYN

예제 출력 1

20

예제 입력 2

2
1
NN
NN

예제 출력 2

-1

예제 입력 3

6
1000
NNYNNN
NNYNNN
YYNYNN
NNYNYY
NNNYNN
NNNYNN

예제 출력 3

3000

힌트

예제 1의 경우에 왕국에는 세 명의 사람들이 살고 있다. 1과 2는 친구이고, 2와 3은 친구이다. 가능한 방법 중 돈을 가장 많이 가진 사람과 적게 가진 사람의 차이의 최댓값은 20이다. 사람 1이 100원을 갖고, 2가 110원을, 3이 120원을 가지면 된다.

예제 2의 경우에는 친구 관계가 없다. 따라서, 아무런 제약이 없기 때문에 정답은 무한대이다.

알고리즘 분류

• 최단 거리 알고리즘

풀이

플로이드-와샬을 사용해서 DP의 최댓값을 구한다. 최댓값이 INF라면 -1을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 51
#define LL long long
#define INF 1e9

using namespace std;
int N, D;
int DP[MAX][MAX];
int answer = 0;

void input() {
	cin >> N;
	cin >> D;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			char S;
			cin >> S;
			if (i == j) {
				continue;
			}
			if (S == 'N') {
				DP[i][j] = INF;
			}
			else if (S == 'Y') {
				DP[i][j] = D;
			}
		}
	}
}

void Settings() {
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (DP[i][j] > DP[i][k] + DP[k][j]) {
					DP[i][j] = DP[i][k] + DP[k][j];
				}
			}
		}
	}
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			answer = max(answer, DP[i][j]);
		}
	}
	if (answer == INF) {
		cout << -1 << "\n";
	}
	else {
		cout << answer << "\n";
	}
}

int main() {
	FASTIO
	input();
	Settings();
	Find_Answer();

	return 0;
}