백준 12875 - 칙령

문제

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

리뷰

플로이드 워셜을 통해 풀이할 수 있는 간단한 문제였다.

주어진 조건을 그래프에 대입해보았을 때 친구관계에서 가장 먼 거리 $\times d$가 답이 된다.
따라서 친구관계일시 간선 비용을 1을 설정해주고 플로이드 워셜을 수행한다음
가장 큰 비용(map[i][j])를 탐색하면 답을 도출할 수 있다.

문제를 풀이함에 있어 유의할 점은 친구관계가 없거나 전체 정점과 형성되지 않는 경우에
무한대로 처리를 해주어야 해서 map의 초기값을 int 범위내에서 적절히 설정해주어야
한다는 점이었다.

로직의 시간 복잡도는 플로이드 워셜의 $O(N^3)$으로 수렴하고 이는 $N=50$인 최악의 경우에도
무난히 제한 조건 2초를 통과한다.

코드

느린 자바 채점 속도가 답답하여 유별나게 cpp로 풀이해보았다.

#include<iostream>
#include<cmath>

#define MAX 1e9
using namespace std;

int map[51][51];
int n, d;

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                if (map[i][k] == MAX || map[k][j] == MAX)
                    continue;

                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
            }
}

int main() {
    cin >> n;
    cin >> d;
    char c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> c;

            if (i == j) {
                map[i][j] = 0;
                continue;
            }

            map[i][j] = c == 'Y' ? 1 : MAX;
        }
    }

    floyd();
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans = max(ans, map[i][j]);

    ans = ans == MAX ? -1 : ans * d;
    cout << ans;
}

결과