[백준 2458번] 키 순서

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

2458번: 키 순서

풀이) 

다수가 그렇듯 직전문제와 비슷한 위상정렬이라 생각했고 접근했다. inDegree를 하나씩 내리면서 가지고 있던 back값들을 앞으로 더해주고  마지막에 1~N까지 돌면서 back[i] + front[i] == N - 1까지를 접근을 했는데 위상정렬로는 해결할 수 없었던 문제였다. 플로이드 와샬로 해결할 수 있었고, i -> j에 대한 거쳐가는 모든 정점을 고려해서 각 정점들의 모든 관계를 업데이트 시킨 후, 관계 N * N 의 관계를 돌면서 해당 i, j의 관계가 존재한다면 각각 front, back에 채워놓고 마지막에 1~N의 정점을 확인할 때 back + front가 N - 1이라는 뜻은 모든 정점에 대한 비교가 되었다는 뜻이기에 해결할 수 있었다.

( * 큰 수를 초기화할때 2e9, 20억을 넣곤 했는데 아무생각 없이 넣었다가 29번줄처럼 int범위를 벗어날 수 있으므로 잘 신경써야한다.) 

#include <iostream>
using namespace std;

int N, M, a, b, result = 0;
int relation[501][501], front[501], back[501];

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

    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            relation[i][j] = 2e8;
    while (M--)
    {
        cin >> a >> b;
        relation[a][b] = 1;
    }
    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (i == j || i == k || j == k)
                    continue;
                relation[i][j] = min(relation[i][j], relation[i][k] + relation[k][j]);
            }
        }
    }
    
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (i == j)
                continue;
            if (relation[i][j] != 2e8)
            {
                front[i]++;
                back[j]++;
            }
        }
    }
    for (int i = 1; i <= N; i++)
        if (front[i] + back[i] == N - 1)
            result++;
    cout << result;
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!