[5일차][그래프] 최소동전 갯수

- 문제 설명

n명이 사람들이 동전을 가지고 있음

최소 갯수는 1개

누구보다 많은지만 알 수 있음

이 때 최대 갯수를 알아내기

- 입력 

1 // 테스트 케이스

3 3 // 3명, 관계 3개(관계란 누가 누구보다 많다)

1 2 1 3 3 2 // 1 < 2, 1 < 3, 3 < 2

- 출력

#1 3 // 테스트케이스, 3개가 최대 갯수

- 입력 예시

3
3 3
1 2 1 3 3 2
5 5
1 2 1 3 4 3 3 2 2 5
6 7
1 2 1 3 3 2 6 3 3 4 5 4 2 5

- 출력 예시

#1 3
#2 4
#3 5

- 코드

#include "stdio.h"

int peopleNum, relation;

int coinRelationGraph[101][101]; // 누가 누구보다 많다라는 관계를 가지는 그래프

int getMoreArray[101]; // 더 많이 가진 사람을 언급할때마다 숫자를 가지는 배열

int queue[101];

int front;

int rear;

int coinNum[101]; // 코인갯수

void findMaxCoinNum();

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        // 큐 초기화

        front = -1;

        rear = -1;

        

        scanf("%d %d",&peopleNum, &relation);

        for(int i =0;i<relation;i++)

        {

            int n1, n2;

            scanf("%d %d",&n1, &n2);

            coinRelationGraph[n1][n2] = 1; // n1 < n2 를 그래프로 표시

            getMoreArray[n2]++; // 더 많이 가진 사람을 언급하면 해당 배열의 숫자를 증가

        }

        findMaxCoinNum();

        

        int max = 0; // 최대 값 초기화

        for( int i=1;i<=peopleNum;i++) // 최대값 찾기

        {

            if(coinNum[i] > max)

                max = coinNum[i];

        }

        printf("#%d %d\n",tc,max); //  결과 출력

        

        for(int i=0;i<=peopleNum;i++) // 초기화

        {

            coinNum[i] = 0;

            getMoreArray[i] =0;

            for(int j=0;j<=peopleNum;j++)

            {

                coinRelationGraph[i][j] = 0;

            }

        }

        

    }

    return 0;

}

void findMaxCoinNum()

{

    // 관계가 0인 모든 노드 enqueue

    for(int i=1;i<=peopleNum;i++) // 관계가 0인애부터 시작

    {

        if(getMoreArray[i]==0)

        {

            queue[++rear] = i; // enqueue

            coinNum[i] = 1; // 맨 처음 아이는 최소 갯수 1개

        }

    }

    while (front != rear) {

        int n = queue[++front]; // dequeue

        //        printf("%d ",n); // 처리 순서 출력

        for(int i=1;i<=peopleNum;i++)

        {

            if(coinRelationGraph[n][i] == 1) // n < i 라면

            {

                getMoreArray[i]--; // 더 많은 사람이었던 i에 대한 관계를 하나 처리했으므로 갯수를 하나 줄임

                

                if(getMoreArray[i] == 0) // 관계가 다 해결되었다면

                {

                    queue[++rear] = i; // i를 큐에 넣고

                    coinNum[i] = coinNum[n]+1; // 이전 사람 보다 하나 더 많은 동전을 가진다.

                }

            }

        }

    }

}