백준 2458 - 키 순서

문제 설명

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 키를 비교한 관계가 M개 주어졌을 때 위치를 정확히 알 수 있는 노드의 개수를 구하면 된다.

 

처음 문제를 보았을 때는 위상 정렬을 통해 풀 수 있다고 생각했다.

하지만 위상 정렬은 느슨한 정렬을 수행하므로 정확한 위치를 알 수 있는 개수를 구하지 못한다.

 

따라서 다른 접근이 필요한데 생각보다 간단하다.

특정 노드 a에서 다른 노드들까지의 거리를 구한다고 해보자.

이때 모든 노드까지의 거리를 구했을 때 그 거리를 모두 알고 있다면 a의 위치는 명확해진다.

따라서 모든 노드 간의 거리를 구했을 때 거리가 구해지는 노드의 개수를 세면 된다.

 

거리를 구하는 과정은 플로이드-와샬 알고리즘을 이용했다.

모든 노드의 거리를 구해야 했기 때문이다.

for (int k = 1; k <= N; k++)
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (dist[i][j] > dist[i][k] + dist[k][j])
            {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

 

이후 거리가 기록된 개수를 세고 그 개수가 N-1개이면 정확한 위치가 구해진 노드로 판정했다.

int ans = 0;
for (int i = 1; i <= N; i++)
{
    int cnt = 0;
    for (int j = 1; j <= N; j++)
    {
        if (dist[i][j] != MAX || dist[j][i] != MAX) cnt++;
    }

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

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
int N, M;
vector<vector<int>> adj;
vector<vector<int>> dist;

int main()
{
    INPUT_OPTIMIZE;

    cin >> N >> M;

    adj.resize(N + 1, vector<int>());
    dist.resize(N + 1, vector<int>(N+1, MAX));

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;

        dist[a][b] = 1;
    }

    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; i++)
    {
        int cnt = 0;
        for (int j = 1; j <= N; j++)
        {
            if (dist[i][j] != MAX || dist[j][i] != MAX) cnt++;
        }

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

    cout << ans;
}

---