[BOJ] 백준 2458 키 순서

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

Approach

 

그래프 관계를 표현 → a가 b보다 작다면 a에서 b로 화살표 표현

 

Q. 자신의 키 순서를 알 수 있는 방법은 무엇이 있을까?

A. 자신보다 키가 큰 사람의 수 x와 작은 사람의 y → x + y = N-1 인 경우입니다.

    즉, 대소 판별이 가능한 수가 N-1명인 경우 자신이 몇번째인지 알 수 있습니다.

* cnt[i] : i번째 학생과 대/소 판별이 가능한 학생 수로 정의

그래프에서 정점별로 방문한 가능한 곳을 탐색하는데 (자기자신 제외, 재방문 X) 

대소 비교가 되었던 학생은 cnt[A]++, cnt[B]++ 처리합니다.

결과적으로 cnt[i] == N-1인 학생들의 수가 대/소 판별이 가능한 학생입니다.

 

시뮬레이션 일부

1번 학생을 기준으로 대/소 비교가 가능한 학생은 2, 4, 5, 6 입니다.

① [1]과 연결된 정점 [5] → cnt[1]++, cnt[5]++ 

    (1번 학생은 5번 학생보다 키가 크고, 5번 학생은 1번 학생보다 작다는 의미에서 각각 cnt[] 값을 올려줍니다.)

② [5]와 연결된 정점 [4], [2]가 있으므로 → cnt[1]++, cnt[4]++ / cnt[1]++, cnt[2]++

    현재 기준은 1번학생이므로 cnt[1]에 대한 수치를 올려줍니다. (현재 cnt[5]가 기준이 아닙니다.)

③ 학생 [2] 입장에서는 더이상 나가는 화살이 없으며 탐색 종료

    학생 [4] 입장에서는 학생 [2]는 이미 방문하였으며 아직 방문하지 않은 학생 [6]이 존재

    → cnt[1]++, cnt[6]++

 

결과적으로 학생 [1]을 기준으로 탐색을 마쳤을 때는 cnt[] = {4 1 0 1 1 1} 입니다.

이를 [1]~[6]까지 순차적으로 기준으로 잡아서 cnt[] 배열을 갱신합니다.

 

cnt[] 배열의 변화

[1] = 4 1 0 1 1 1

[2] = 4 1 0 1 1 1

[3] = 4 2 3 2 1 2

[4] = 4 3 3 4 1 3

[5] = 4 4 3 5 4 4

[6] = 4 4 3 5 4 4

▶ 결과적으로 cnt[i] = N - 1 = 5인 값은 학생[4]로 1명뿐입니다.

 

이러한 학생들의 키 정보를 인접 행렬 혹은 인접리스트로 구현할 수 있는데

이 문제의 경우, N ≤ 500이므로 크기를 고정하는 인접행렬로 처리가능합니다.

시간 복잡도 O (N × N)

 

인접 리스트를 이용한 풀이 [Jungol] 2462 키 순서 참고

[Jungol] 정올 2462 키 순서

---

#include <stdio.h>
 
const int LM = 510;
int N, M, ans;
int info[LM][LM], cnt[LM];
bool visit[LM];
 
void input() {
    scanf("%d %d", &N, &M);
    int i, u, v;
    for (i = 0; i < M; i++) {
        scanf("%d %d", &u, &v);
        // u->v : u보다 v가 더 크다.
        info[u][v] = 1;  
    }
}
 
void init(bool* arr) {
    for (int i = 0; i < LM; i++) {
        arr[i] = false;
    }
}
 
void DFS(int src, int now) {
    if (src != now) { // 자기 자신 제외
        cnt[src]++;
        cnt[now]++;
    }
    visit[now] = true;
    for (int i = 1; i <= N; i++) {
        // 아직 방문하지 않으면서 now가 i보다 큰 경우
        if (!visit[i] && info[now][i]) {   
            DFS(src, i);
        }
    }
}
 
void process() {
    int i;
    for (i = 1; i <= N; i++) {
        // 매 기준마다 방문표시 초기화
        init(visit);
        DFS(i, i);
    }
    for (i = 1; i <= N; i++) {
        if (cnt[i] == N - 1) ans++;
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    process();
    printf("%d\n", ans);
}