[10일차][그래프] 최장거리 구하기

- 문제 설명

0->N노드로 가는 최장거리 구하기

위의 경우 4 + 8 + 1 로 13이다.

- 입력

1 // 테스트 케이스

4 7 // N, 엣지 갯수

0 1 4 // 출발, 도착, 거리

0 4 5

1 2 8

1 3 3

2 4 1

3 4 4

- 출력

#1 13 // 테스트케이스, 최장거리

- 입력 예시

3
2 3
0 1 1
0 2 1
1 2 6
4 7
0 1 9
0 2 3
0 3 7
1 4 2
2 3 8
2 4 1
3 4 8
4 6
0 1 10
0 2 7
1 4 2
2 3 10
2 4 3
3 4 10

- 출력 예시

#1 7
#2 19
#3 27

- 코드

#include "stdio.h"

int N, E;

int graph[1001][1001];

int destinationNum[1001];

int distance[1001];

void findMaxDistance();

int front, rear;

int queue[1000001];

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",&N,&E);

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

        {

            distance[i] = 0; // distance값 초기화

            destinationNum[i] = 0; // 종착지 갯수 표시 배열 초기화

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

            {

                graph[i][j] =0;

            }

        }

        for (int i = 1; i<=E;i++) // 엣지 갯수 만큼

        {

            int n1, n2, w;

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

            graph[n1][n2] = w; // 갈 수 있는 비용 입력

            destinationNum[n2]++; // 종착지 언급 시 숫자 증가

        }

        findMaxDistance();

        printf("#%d %d\n", tc,distance[N]); // 마지막 노드의 비용 출력

    }

    return 0;

}

void findMaxDistance()

{

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

    {

        if(destinationNum[i] == 0) // 종착지로 언급되지 않은 애들부터 시작

        {

            // enqueue

            queue[++rear]  = i;

            distance[i] = 0;

        }

    }

    while(front != rear) // 큐에 있는 경우

    {

        // dequeue

        int startNode = queue[++front];

        

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

        {

            if(graph[startNode][i]) // startNode -> i로 갈 수 있다면

            {

                distance[i] = (distance[i] > graph[startNode][i] + distance[startNode]) ? distance[i] : graph[startNode][i] + distance[startNode];// 현재 distance에 저장된 값이 startNode에서 i로 오는 값보다 작으면 갱신해줌

                

                destinationNum[i]--; // i로 가는 것을 처리 했으므로 해당 종착지 언급을 하나 줄임

                

                if(destinationNum[i] == 0) // i로 오는 것을 모두 처리했다면

                {

                    //enqueue

                    queue[++rear] = i;

                }

            }

        }

    }

}