[7주차] 최단 경로

본 글은 건국대학교 알고리즘 동아리 AlKon 스터디 5조에서 진행된 발표 내용입니다.

 

2458 키 순서

2458번: 키 순서

 

시간 제한	입력	범위
1초	N, M, a, b	2 ≤ N ≤ 500 // 0 ≤ M ≤ N(N-1)/2

 

N: 학생의 수

M: 키를 비교한 회수

a, b: a번 학생이 b번 학생보다 키가 작다.

 

문제: 자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력하라.

 

---

접근법

아직 문제만 보고 알고리즘을 떠올리는 게 쉽지가 않아서 플로이드-워셜을 어떻게 써야하지..?부터 생각했다.

 

세 노드(i, j, k)가 있을 때, i 에서 j 로 가는 경로는 두 가지가 존재한다.

1. i → j
2. i → k → j

해당 문제에서는 a보다 b가 큰 값(더 큰 키)을 가질 때 a에서 b로 향하는 경로가 있다고 한다. d[a][b] = true

bool 이중 배열, d[i][j]=true는 i에서 j로 가는 간선이 존재한다는 의미이다. 해당 문제에서는 i보다 j의 키가 크다는 것을 의미한다.

 

아래 그림으로 예를 들어보자.

 

그래프 정보 갱신

i, j, k라는 세 명의 학생이 있고, 키를 2번 비교했다. i보다 k의 키가 크고, k보다 j의 키가 크다.

 

사람이라면 직관적으로 i보다 j의 키가 크다는 것을 알 수 있을 것이다.

하지만, 컴퓨터는 이를 어떻게 알아야 할까?

 

여기서 Floyd-Warshall 알고리즘을 적용할 수 있다.

 

현재, 그래프 정보는 다음과 같다. (0: false, 1: true)

d[a][b]	i	k	j
i	0	1	0
k	0	0	1
j	0	0	0

d[i][j]를 갱신해보자.

최단 경로를 구하는 플로이드-워셜 알고리즘의 경우, 기존 d[i][j] 값과 k 노드를 경유하는 길이인 d[i][k]+d[k][j] 값을 비교하여 더 작은 값으로 갱신한다.

이것을 어떻게 이용할 수 있을까?

 

답은 앞에서 이미 언급한 바 있다.

i보다 k의 키가 크고, k보다 j의 키가 크다. 따라서, i보다 j의 키가 크다.

i와 j의 직접적인 대소관계를 알지 못 하더라도(d[i][j]=false),

d[i][k]가 true이고 d[k][j]가 true라면, d[i][j]도 true가 된다.

 

이를 바탕으로 그래프 정보를 갱신하면, 다음과 같다.

d[a][b]	i	k	j
i	0	1	1
k	0	0	1
j	0	0	0

d[i][j] 값이 갱신됨으로써, i보다 j가 크다는 사실도 표시된다.

 

자신이 키가 몇 번째인지 알 수 있는 학생

당연하게도, 나를 제외한 모두와 키의 대소 구분이 가능해야 한다.

나를 m번 노드라고 할 때, 그 값이 1(true)인 d[a][m] 또는 d[m][b]의 수가 N-1이면, 위 조건을 충족한다.

 

백준 2458번의 문제 예시의 경우, 플로이드-워셜 알고리즘 수행 후 결과는 다음과 같다.

 

4번 노드와 5번 노드로 자신의 키가 몇 번째인지 알 수 있는지를 알아보자.

 

1. 4번 노드

값이 1인 d[a][4] 혹은 d[4][b]의 개수를 센다.

d[1][4], d[3][4], d[5][4], d[4][2], d[4][6]으로 총 5개이다.

이는 N-1과 같으므로 4번 학생은 자신의 키가 몇 번째인지 알 수 있다.

 

2. 5번 노드

값이 1인 d[a][5] 혹은 d[5][b]의 개수를 센다.

d[1][5], d[5][2], d[5][4], d[5][6]으로 총 4개이다. 이는 N-1과 다르다.

따라서, 5번 학생은 자신의 키가 몇 번째인지 알 수 없다.

5번 학생은 3번 학생과 키의 대소를 비교할 수 없다.

 

---

알고리즘

1. 그래프 정보를 입력한다.
   • a b가 입력되었을 때, d[a][b] 값을 true로 갱신한다.
   • d[b][a] 값은 변하지 않는다.
2. 플로이드-워셜 알고리즘을 수행한다.
   • i보다 k의 키가 크고, k보다 j의 키가 크면 i보다 j의 키가 크다.
   • d[i][k]가 true이고 d[k][j]가 true라면, d[i][j]도 true가 된다.
3. 각 학생에 대하여, 자신이 키가 몇 번째인지 알 수 있는지 판단한다.
   • 키의 대소 비교가 가능한 학생의 수를 세고, N-1과 같다면 자신의 키가 몇 번째인지 알 수 있다.

 

---

시간복잡도

입력 - O(M)

플로이드-워셜 - O(N^3)

대소 비교 가능 여부 count - O(N^2)

 

→ O(N^3)

 

---

제출

맞았습니다!!

 

---

Code - C++

코드를 보기 전에 스스로 구현해 보는 것을 권장합니다.

#include <iostream>
using namespace std;

bool d[501][501]={false,};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        d[a][b] = true;
    }

    // floyd-warshall
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(d[i][k] && d[k][j]) d[i][j] = true;

    int ans=0;
    for(int i=1; i<=n; i++){
        int cnt=0;
        for(int j=1; j<=n; j++)
            if(d[i][j] || d[j][i]) cnt++;

        if(cnt==n-1) ans++;
    }

    cout << ans;
    return 0;
}