[7일차][최소신장트리] 최소신장트리

- 문제 설명

0~N번까지 노드를 가진 그래프

최소 신장 트리의 비용을 모두 더해 출력하시오

N은 1천개

E는 100만개까지 가능

- 입력

1 // 테스트 케이스

2 3 // 노드번호 0~2까지, 엣지 3개

0 1 1 // 0과 1사이 비용 1

0 2 1 // 0과 2사이 비용 1

1 2 6 // 1과 2사이 비용 6

- 출력

#1 2 //테스트케이스, 최소비용

- 입력 예시

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 2
#2 13
#3 22

- 코드

#include "stdio.h"

 

int N, E; // 노드 갯수, 그래프 갯수

int represent[1001]; // 대표 노드

void checkRepresent(int startNode, int endNode);

int kruscal();

int dequeue[3]; // dequeue한 값이 저장되는 배열

int queue[1000002][3]; // 큐

int front;

int rear;

void enQ(int startNode, int endNode, int value);

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

    int T;

    scanf("%d", &T);

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

    {

        front = 0;

        rear = 0;

        scanf("%d %d",&N, &E);

        for (int i = 0; i<=N;i++) // 대표노드 배열 초기화

        {

            represent[i] = i;

        }

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

        {

            int inputStartNode, inputEndNode, value;

            scanf("%d %d %d",&inputStartNode, &inputEndNode, &value);

            enQ(inputStartNode, inputEndNode, value);

        }

 

        printf("#%d %d\n", tc,kruscal());

    }

    return 0;

}

void enQ(int startNode, int endNode, int value)

{

    // enqueue

    int c = ++rear; // 자식 번호

    int p = c/2; // 부모 번호

    queue[c][0] = startNode;

    queue[c][1] = endNode;

    queue[c][2] = value;

     

    while(c>1 && queue[c][2] < queue[p][2]) // 자식의 가중치가 부모의 가중치

보다 작을 때

    {

        // swap

        int tmp;

        tmp = queue[p][0];

        queue[p][0] = queue[c][0];

        queue[c][0] = tmp;

         

        tmp = queue[p][1];

        queue[p][1] = queue[c][1];

        queue[c][1] = tmp;

         

        tmp = queue[p][2];

        queue[p][2] = queue[c][2];

        queue[c][2] = tmp;

         

        c = p;

        p = c/2;

    }

}

void deQ()

{

    // 맨 첫번째를 dequeue 배열에 넣기

    dequeue[0] = queue[1][0];

    dequeue[1] = queue[1][1];

    dequeue[2] = queue[1][2];

     

    // 맨 마지막 노드를 첫번째 노드로

    queue[1][0] = queue[rear][0];

    queue[1][1] = queue[rear][1];

    queue[1][2] = queue[rear][2];

    rear--;

    int p = 1; // 맨 위부터 시작

    while(p <= rear)

    {

        int ch1 = p*2;

        int ch2 = p*2+1;

        if(ch2 <= rear) // 완벽 이진트리인 경우

        {

            // 둘중 작은거랑 부모랑

            int ch = (queue[ch1][2] < queue[ch2][2]) ? ch1 : ch2;

            if(queue[ch][2] < queue[p][2]) // 부모랑 비교해서 자식이 더 작으면

            {

                //swap

                int tmp;

                tmp = queue[ch][0];

                queue[ch][0] = queue[p][0];

                queue[p][0] = tmp;

                 

                tmp = queue[ch][1];

                queue[ch][1] = queue[p][1];

                queue[p][1] = tmp;

                 

                tmp = queue[ch][2];

                queue[ch][2] = queue[p][2];

                queue[p][2] = tmp;

                 

                p = ch; // 부모노드랑 바꿨으므로

            }

            else

                break;

        }

        else if(ch1 <= rear) // 왼쪽 자식만 존재하는 경우

        {

            if(queue[ch1][2] < queue[p][2]) // 부모랑 비교해서 자식이 더 작으면

            {

                //swap

                int tmp;

                tmp = queue[ch1][0];

                queue[ch1][0] = queue[p][0];

                queue[p][0] = tmp;

                 

                tmp = queue[ch1][1];

                queue[ch1][1] = queue[p][1];

                queue[p][1] = tmp;

                 

                tmp = queue[ch1][2];

                queue[ch1][2] = queue[p][2];

                queue[p][2] = tmp;

                 

                p = ch1; //  부모노드랑 바꿨으므로

            }

            else

                break;

 

        }

        else

            break;

    }

     

}

int kruscal() // 크루스칼 알고리즘은 정렬된 상태만 받을 수 있다. enqueue와

dequeue시 힙정렬을 통해 정렬된 값을 가져올 수 있다.

{

    int sum = 0;

    int count = 1;

    while(count <= N)

    {

        // dequeue

        deQ();




// dequeue한 값을 가져옴

        int startNode, endNode, value;

        startNode = dequeue[0];

        endNode = dequeue[1];

        value = dequeue[2];




        if(represent[startNode] != represent[endNode]) // 같은 대표 노드를

가지지 않을 경우

        {

            checkRepresent(startNode, endNode); // 대표 노드 체크

            sum+=value;

            count++;

        }

    }

    return sum;

}

void checkRepresent(int startNode,int endNode)

{

    int lastValue = represent[endNode]; // endNode값 저장

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

    {

        if(lastValue == represent[i]) // endNode값이랑 같은 값을 가지는 것을 모두

찾아

        {

            represent[i] = represent[startNode]; // 대표값을 startNode로 바꿔줌

(서로 이어졌기 때문)

        }

    }

}