BOJ 12875 - 칙령 링크
(2023.05.18 기준 G4)

문제

N명의 사람과 사람 간의 친구 관계가 주어진다. 그리고 모든 사람은 친구가 가지고 있는 돈과 최대 d원 만큼 차이가 날 수 있을 때, 돈을 가장 많이 가진 사람과 적게 가진 사람의 차이가 가장 크게 됐을 때에 차이 출력

알고리즘

플로이드 워셜

풀이

일단 직접 친구인 관계는 d원 만큼 차이가 날 수 있을 것이다.
그러면 한 사람 건너 친구인 관계는? d * 2원 만큼 차이가 날 수 있다.
이는 즉, 친구인 관계는 거리를 1로 두고 아니면 inf로 둔 거리 행렬을 플로이드 워셜을 돌려 친구 관계의 거리만큼 차이가 날 수 있는 것이다.

최대한 차이가 나게 해야 하므로 거리가 가장 큰 값에 d를 곱한 수가 답이 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, d;
    cin >> N >> d;

    // 직접 친구인 관계 간 거리는 1
    int dist[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dist[i][j] = inf;
    for (int i = 0; i < N - 1; i++){
        string relationship;
        cin >> relationship;
        for (int j = i + 1; j < N; j++) if (relationship[j] == 'Y') dist[i][j] = dist[j][i] = 1;
    }

    // 플로이드 워셜
    for (int k = 0; k < N; k++){
        dist[k][k] = 0;
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }

    // 가장 먼 관계의 거리
    int max_dist = 0;
    for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++)
        max_dist = max(max_dist, dist[i][j]);

    // 거리 * d만큼의 차이가 날 수 있다.
    if (max_dist < inf) cout << max_dist * d;
    else cout << -1;
}

• Python

import sys; input = sys.stdin.readline
from math import inf

N = int(input())
d = int(input())
relationship = [input().strip() for _ in range(N)]

# 직접 친구인 관계 간 거리는 1
dist = [[inf] * N for _ in range(N)]
for i in range(N - 1):
    for j in range(i + 1, N):
        if relationship[i][j] == 'Y':
            dist[i][j] = dist[j][i] = 1

# 플로이드 워셜
for k in range(N):
    dist[k][k] = 0
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# 가장 먼 관계의 거리
max_dist = max(dist[i][j] for i in range(N - 1) for j in range(i + 1, N))

# 거리 * d만큼의 차이가 날 수 있다.
print(max_dist * d) if max_dist < inf else print(-1)