백준 2458 키 순서

문제링크 : https://www.acmicpc.net/problem/2458

아이디어

• 각 노드의 순서를 구하기
• 만약 구체적인 순서를 묻지 않았다면 topo
  • topo는 구체적인 수치는 알 수 없음
• floyd해서, 각 원소가 앞에있는지 위에있는지 확인
  • 이때, 확인되지 않은 원소가 있을경우, 모르는것

시간복잡도 계산

• 플로이드 : O(N^3), 125e6 > 1e8 > 가능

자료구조

• 앞인지 뒤인지 확인 배열 : int map[510][510]
  • -1 : 아직 모르는 상태
  • 0 : 작음, map[a][b] =0 = a가 b보다 작음
  • 1 : 큼, map[a][b] = 1 = a가 b보다 큼

코드(C++)

#include <iostream>
 
using namespace std;
 
int map[510][510];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin>> N >> M;
    fill(&map[0][0], &map[509][510], -1);
    
    for(int i=0; i<M; i++) {
        int a,b; cin >> a >> b;
        map[a][b] = 0;
        map[b][a] = 1;
    }
    
    for(int i=1; i<=N; i++) map[i][i] = 1;
    
    // floyd 수행
    for(int k=1; k<=N; k++) {
        for(int j=1; j<=N; j++) {
            for(int i=1; i<=N; i++) {
                if(map[j][i] == -1) {
                    // j가 k보다 크고, k가 i보다 크면, j는 i 보다 큼
                    if(map[j][k] ==1 && map[k][i] == 1) map[j][i] = 1;
                    // j가 k보다 작고, k가 i보다 작으면, j는 i 보다 작음
                    if(map[j][k] ==0 && map[k][i] == 0) map[j][i] = 0;
                    
                }
            }
        }
    }
    
    int cnt=0;
    for(int j=1; j<=N; j++) {
        int ecnt = 0;
        for(int i=1; i<=N; i++) {
            if(map[j][i] == -1) break;
            ecnt++;
        }
        if(ecnt == N) cnt++;
    }
    
    cout << cnt << '\n';
    
    return 0;
}
 

문제유형

• 플로이드 - 몇번째 순서인지 구하는 문제
  • topological sort는 전체 순서는 맞지만, 내가 몇번째 순서인지 정확히 알수는 없음
    • 예시 : 1번 노드가 2번쨰 순서도 정답이고 3번째 순서도 정답임
  • floyd로 모든 케이스 비교해서 구할 수 있음
    • map[j][k] = 1 && map[k][i] ==1 >> map[j][i] =1