본문 바로가기

Dev/Algorithm

[백준] 2458 - 키 순서

반응형

www.acmicpc.net/problem/2458

 

2458번: 키 순서

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

www.acmicpc.net

 문제만 읽어서는 감이 잘 오질 않는데, 결과적으로 본인의 키가 몇번째인지를 알려면 기술되어있는 N명의 '학생중 자신보다 키가 작은 학생의 수 + 자신보다 키가 큰 학생의 수 = N-1'이 되면 되는데, 이건 플로이드-워셜 알고리즘을 조금 응용하면 문제를 풀 수 있다. 알고리즘에 대한 설명은 나보다는 위키가 훨씬 더 잘 알려주니...

ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고

ko.wikipedia.org

#include <stdio.h>
#include <string.h>
#define UNKNOWN 0x00
#define TALL 1
#define SMALL -1

int N, M;
int floid[501][501];

int main()
{
    memset(floid, UNKNOWN, sizeof(floid));
    scanf("%d%d", &N, &M);

    for (int i = 0; i < M; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        floid[a][b] = TALL;
        floid[b][a] = SMALL;
    }

    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (floid[i][j] == UNKNOWN)
                {
                    if (floid[i][k] == TALL && floid[k][j] == TALL)
                        floid[i][j] = TALL;
                    if (floid[i][k] == SMALL && floid[k][j] == SMALL)
                        floid[i][j] = SMALL;
                }
            }
        }
    }

    int answer = 0;
    for (int i = 1; i <= N; i++)
    {
        bool existUNKNOWN = false;
        for (int j = 1; j <= N; j++)
        {
            if (i != j && floid[i][j] == UNKNOWN)
            {
                existUNKNOWN = true;
                break;
            }
        }
        if (!existUNKNOWN)
        {
            answer += 1;
        }
    }

    printf("%d\n", answer);
    return 0;
}
반응형