[백준/C++] 12875. 칙령

플로이드 와샬을 계속 공부해보자. 이번에는 최고의(?) 전제군주국으로 가보자.

칙령

플로이드 와샬은 알고리즘만 잘 외우고 있거나 혹은 행렬을 그려보면 쉽다. 플로이드 와샬 알고리즘을 돌려서 제일 멀리 연결된 엣지수*d 를 하면 될 것 같습니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n, d;
const int MAX = 50;
int map[51][51] = {0, };

int main(){
    cin>>n;
    cin>>d;

    for(int i = 0; i<51; i++){
        for(int j = 0; j<51; j++){
            if(i!=j){
                map[i][j] = MAX;
            }
        }
    }

    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=n; j++){
            char c;
            cin>>c;
            if(c == 'Y'){
                map[i][j] = 1;
            }
        }
    }

    for(int k = 1; k<=n; k++){
        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=n; j++){
                if(map[i][j] > map[i][k] + map[k][j]){
                    map[i][j] = map[i][k] + map[k][j];
                }
            }
        }
    }

    int max_edge = 0;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=n; j++){
            max_edge = max(max_edge, map[i][j]);
        }
    }

    if(max_edge == MAX){
        cout<<-1<<endl;
    }
    else{
        cout<<max_edge*d<<endl;
    }
}

만약에 범위 내에서 계속 탐색했는데 MAX값만 나온다면 그것은 모두가 연결되지 않았다는 뜻이므로 무한대를 뜻하는 -1 을 출력해주자.
오늘도 화이팅><