BOJ : 2458 키 순서

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

github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2458.cpp

출처

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2011 > 초등부 4번

갓초등부 문제치고는 쉬운 문제다.

플로이드 와샬 알고리즘을 이용해 각 노드의 연결 여부를 판단하고 자신의 키가 몇 번째 인지 아는 학생 (모든 연결고리를 가지고 있는 학생. 즉, 반복문을 돌린 배열에서 본인 노드가 N이라면 (N, Y)와 (X, N)이 모두 true인 노드)의 개수를 출력해주면 된다.

굳이 일일이 연결된 수를 계산안하고 bool 배열로 true 값만 찾아줘도 됩니다.

#include <stdio.h>
#define INF 987654321
    int N,M,ans=0;
    int arr[505][505];
    int isConnected[505]={0,};

int main(){
    
    scanf("%d%d",&N,&M);
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            arr[i][j] = INF;
        }
    }
    
    while(M--){
        int a,b;
        scanf("%d%d",&a,&b);
        arr[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(arr[i][j] > arr[i][k]+arr[k][j])
                    arr[i][j] = arr[i][k]+arr[k][j];
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(arr[i][j]!=INF) {
                isConnected[i]++, isConnected[j]++;
                if(isConnected[i]==N-1) ans++;
                if(isConnected[j]==N-1) ans++;
            }
        }
    }

    printf("%d",ans);
}