[BOJ] 키 순서

[문제]

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

2458번: 키 순서

[풀이]

2458

맞았습니다!!

2968

132

C++14 / 수정

1316

1분 전

 

1) 플로이드 와샬 알고리즘 사용 (줄 세우기 처럼 위상정렬을 사용하면 4가 제일 커버림)

 

2) 플로이드 와샬 알고리즘을 사용해서 모든 최단 경로를 구해준다. 

(플로이드 와샬 알고리즘 개념은 (https://hsp1116.tistory.com/45) 를 참고했다)

" 플로이드-워셜은 optimal substructure의 개념을 이용하여 최단 경로를 찾는다. optimal substructure란 특정 경로 안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념이다."

 

3) 플로이드 와샬을 사용하여 구한 taller[i][j]에는 각 정점으로 가는 최단 경로가 저장되어있다. 하지만 INF인 경우에는 경로가 존재하지 않다는 것이다. 

-> 존재하지 않는다 =  내가 얘보다 키가 큰지 작은지 모른다. 

그런 노드들은 flag를 false로 한 후에 flag가 true 인 수를 구하면 정답이다.

 

---

#include <iostream>
#include <cstring>
#include <cmath>
 
#define MAX_N 501
#define INF 987654321
using namespace std;
 
//키 순서 -플로이드 와샬 알고리즘
int taller[MAX_N][MAX_N]; //키 비교를 위한 배열
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            taller[i][j] = i == j ? 0 : INF; //같은 사람일 경우에는 0 / 아닌 경우에는 최소값 비교하기 수월하게 가장 큰 값을 넣어준다.
 
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        taller[a][b] = 1; //a< b
    }
    //입력
 
    //플로이드 와샬 알고리즘
    //시간복잡도 유의 (n^3)
    for (int a = 1; a <= n; a++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                taller[i][j] = min(taller[i][j], taller[i][a] + taller[a][j]); //i< a , a < j -> i < j
            }
        }
    }
 
    bool flag[MAX_N]; //INF인 경우에는 비교할 수 없는 사람임
    memset(flag, true, sizeof(flag));
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (taller[i][j] == INF) {
                if (taller[j][i] == INF)  {
                    flag[i] = false;
                    break;
                }
            }        
        }
    }
 
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (flag[i]) cnt++;
    }
 
    cout << cnt << '\n';
    return 0;
}