[C/C++] 백준 #2458 키 순서(플로이드 워샬)

#2458은 n명의 사람들중에 일부 사람들끼리 키를 비교해서 그 결과를 아는 경우에, 정확하게 자신이 몇번째 키 순서를 가졌는지 알 수 있는 사람들의 숫자를 구하라는 문제입니다.

 

height comparision

 

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

2458번: 키 순서

 

처음에 접근한 방법은 위상정렬이었습니다.  하지만 위상정렬로 처리하기에는 한계가 있어서 플로이드 워샬 알고리즘을 변형해서 사용하기로 했습니다.  플로이드 워샬은 그래프에서 모든 노드간의 최소 비용 경로값을 계산해주는 알고리즘으로 \(O(N^3)\) 알고리즘입니다.  당연히 노드수가 많으면 시간초과가 걸립니다.

 

플로이드 워샬 알고리즘 설명은 다음 링크를 참고해주세요.

https://sdev.tistory.com/755

[C/C++] 백준 #1613 역사(플로이드 와샬)

 

플로이드 워샬은 최적의 경로값을 계산하는 것이지만, 저는 둘 사이의 경로가 존재하는지만 검사하도록 했습니다.  만약 "홍길동"이 "이몽룡"보다 크고, "이몽룡"이 "성춘향"보다 크다면, 이 관계에서 "홍길동"은 "성춘향"보다 크다는 것을 알 수 있습니다.  여기서 주의할 점은 만약 크다 관계가 이어져있어야 한다는 것입니다.  "홍길동"이 "성춘향"보다 크고 "이몽룡"이 "성춘향"보다 크다면, "홍길동"과 "이몽룡" 사이의 키 비교관계가 만들어질 수 없습니다.  그래서 반드시 유향그래프로 만들어져 있어야 합니다.

 

다음으로는 어느 한 사람이 자신을 제외한 모든 사람들과의 관계가 주어졌다면(그것이 큰 관계이든 작은 관계이든) 자신이 위치해야 하는 정확한 자리를 얻어올 수 있습니다.  사실 위상정렬로 따지면, 어떤 순서로 정렬을 잡든 이 사람의 위치는 항상 같은 위치를 차지하게 됩니다.  즉, 이 문제는 위상정렬을 실행했을 때, 절대 위치가 바뀌지 않는 노드의 개수를 물어보는 것과 같은 문제입니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2458 - Height Order
//        - by Aubrey Choi
//        - created at 2019-07-09
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

int main()
{
    int n, m, a, b, ans = 0, i, j, k, s;
    char d[501][501];
    memset(d, 0, sizeof(d));
    scanf("%d%d", &n, &m);
    while(m--) { scanf("%d%d", &a, &b); d[a][b] = 1; }
    for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++)
    {
        if(i == j || d[i][j]) continue;
        if(d[i][k] && d[k][j]) d[i][j] = 1;
    }
    for(i=1; i<=n; i++)
    {
        for(j=1,s=0; j<=n; j++) if(d[i][j] || d[j][i]) s++;
        if(s==n-1) ans++;
    }
    printf("%d\n", ans);
}