글 읽기 - [C] 어찌저찌 통과는 했는데... 궁금한점이 있습니다.

irsam78 2년 전 0

저는 왜 틀린건지 잘 모르겠어서 질문 남겨봅니다.

아래에 정답 코드와 오답 코드를 적어두었습니다.

기본적으로 다익스트라를 사용했고 그래프의 구현은 인접 리스트를 이용했습니다. 시간 문제 때문에 다익스트라에서 힙을 이용해서 최소 비용 지점을 찾았습니다.

힙은 다름 문제에서 맞았습니다 받은걸 기반으로 해서 문제가 없을텐데 그럼 다익스트라에서 문제가 있겠지만 그걸 잘 모르겠습니다.

도움주시면 정말 감사하겠습니다.

///맞았습니다
#include<stdio.h>
#include<malloc.h>

#define MAX_V 20000
#define MAX_E 300000
#define MARGIN 1
#define INF -1

typedef struct{
    int node;
    int cost;
}heapNode;

typedef struct node{
    int from, to, weight;
    struct node *next;
}Node;

Node* Graph[MAX_V+MARGIN];

void Dijkstra(int minList[], int maxV, int str);

int main(){
    int V, E;
    int K;
    int u, v, w;
    Node *nowNode, *tmp;
    int i;
    int minList[MAX_V+MARGIN];

    scanf("%d %d", &V, &E);
    scanf("%d", &K);
    for(i = 0;i < E;i++){
        scanf("%d %d %d", &u, &v, &w);

        nowNode = (Node*)malloc(sizeof(Node));

        nowNode->from = u;
        nowNode->to = v;
        nowNode->weight = w;

        nowNode->next = Graph[u];
        Graph[u] = nowNode;

    }

    for(i = 0;i <= V;i++){
        minList[i] = INF;
    }

    Dijkstra(minList, V, K);

    for(i = 1;i <= V;i++){
        if(minList[i] == INF)
            puts("INF");
        else
            printf("%d\n", minList[i]);
        
        nowNode = Graph[i];
        while(nowNode){
            tmp = nowNode;
            free(tmp);
            nowNode = nowNode->next;
        }
    }

    return 0;
}

int compare(heapNode *n1, heapNode *n2){
    if(n1->cost > n2->cost)
        return -1;
    else if(n1->cost < n2->cost)
        return 1;
    else
        return 0;
}
void reheapUp(heapNode* list[], int end){
    int parent, now;
    heapNode *tmp;

    now = end;
    parent = (now-1)/2;
    if(!(parent >= 0))
        return;

    while(now > 0 && compare(list[parent], list[now]) <= 0){
        tmp = list[parent];
        list[parent] = list[now];
        list[now] = tmp;
        
        now = parent;
        parent = (now-1)/2;
        if(!(parent >= 0))
            return;

    }
}
void reheapDown(heapNode* list[], int end){
    int now, child, child1, child2;
    heapNode *tmp;

    now = 0;
    child1 = 2*now+1;  child2 = 2*now+2;
    if(!(child1 <= end || child2 <= end)){
        return;
    }
    child = compare(list[child1], list[child2]) >= 0 ? child1 : child2;
    while(now < end && compare(list[now], list[child]) <= 0){
        tmp = list[now];
        list[now] = list[child];
        list[child] = tmp;
        
        now = child;
        child1 = 2*now+1;  child2 = 2*now+2;
        if(!(child1 <= end || child2 <= end)){
            return;
        }
        child = compare(list[child1], list[child2]) >= 0 ? child1 : child2;
    }
}

void Dijkstra(int minList[], int maxV, int str){
    int i;
    int nowV;
    Node *nowNode;
    heapNode* heapMinList[MAX_E+MARGIN];    int end = -1;
    int check[maxV+MARGIN];

    for(i = 0;i <= maxV;i++){
        check[i] = 0;
    }

    nowV = str;
    nowNode = Graph[nowV];

    minList[str] = 0;

    heapMinList[++end] = (heapNode*)malloc(sizeof(heapNode));
    heapMinList[end]->node = nowV;
    heapMinList[end]->cost = minList[nowV];
    
    while(end > -1){
        nowV = heapMinList[0]->node;
        free(heapMinList[0]);
        nowNode = Graph[nowV];

        heapMinList[0] = heapMinList[end--];
        reheapDown(heapMinList, end);

        if(check[nowV] == 0){
            while(nowNode){
                if(check[nowNode->to] == 0 && (minList[nowNode->to] == INF || minList[nowV]+nowNode->weight < minList[nowNode->to])){
                    minList[nowNode->to] = minList[nowV]+nowNode->weight;

                    heapMinList[++end] = (heapNode*)malloc(sizeof(heapNode));
                    heapMinList[end]->node = nowNode->to;
                    heapMinList[end]->cost = minList[nowNode->to];

                    reheapUp(heapMinList, end);
                }

                nowNode = nowNode->next;
            }

            check[nowV] = 1;
        }
    }
}

///틀렸습니다
#include<stdio.h>
#include<malloc.h>

#define MAX_V 20000
#define MAX_E 300000
#define MARGIN 1
#define INF -1

typedef struct node{
    int data[2];//[0] 가중치, [1] 향하는 지점
    struct node *next;
}Node;

Node *Adjacent[MAX_V+MARGIN];

void process(int V, int start, int minList[]);

int main(){
    int V, E;
    int start;
    int u, v, w;    Node *node, *now;
    int minList[MAX_V+MARGIN], i;

    scanf("%d %d", &V, &E);
    scanf("%d", &start);
    for(i = 0;i < E;i++){
        scanf("%d %d %d", &u, &v, &w);

        node = (Node*)malloc(sizeof(Node));
        node->data[0] = v;   node->data[1] = w;
        node->next = NULL;

        if(Adjacent[u] == NULL)
            Adjacent[u] = node;
        else{
            now = Adjacent[u];
            while(now->next != NULL){
                now = now->next;
            }
            now->next = node;
        }
    }

    for(i = 0;i <= V;i++){
        minList[i] = INF;
    }
    
    process(V, start, minList);
    
    for(i = 1;i <= V;i++){
        if(minList[i] == INF)
            puts("INF");
        else
            printf("%d\n", minList[i]);
    }

    return 0;
}
int compare(int n, int m){
    if(n == INF)
        return -1;
    else if(m == INF)
        return 1;
    else{
        if(n > m)
            return -1;
        else if(n < m)
            return 1;
        else
            return 0;
    }
}
void reheapUp(int list[][2], int end){
    int parent, now;
    int tmp;

    now = end;
    parent = (now-1)/2;
    if(!(parent >= 0)){
        return;
    }
    while(now > 0 && compare(list[parent][1], list[now][1]) == -1){
        tmp = list[parent][0];
        list[parent][0] = list[now][0];
        list[now][0] = tmp;

        tmp = list[parent][1];
        list[parent][1] = list[now][1];
        list[now][1] = tmp;
        
        now = parent;
        parent = (now-1)/2;
        if(!(parent >= 0)){
            return;
        }
    }
}
void reheapDown(int list[][2], int end){
    int now, child, child1, child2;
    int tmp;

    now = 0;
    child1 = 2*now+1;  child2 = 2*now+2;
    if(!(child1 <= end || child2 <= end)){
        return;
    }
    child = compare(list[child1][1], list[child2][1]) == 1 ? child1 : child2;
    while(now < end && compare(list[now][1], list[child][1]) == -1){
        tmp = list[now][0];
        list[now][0] = list[child][0];
        list[child][0] = tmp;

        tmp = list[now][1];
        list[now][1] = list[child][1];
        list[child][1] = tmp;
        
        now = child;
        child1 = 2*now+1;  child2 = 2*now+2;
        if(!(child1 <= end || child2 <= end)){
            return;
        }
        child = compare(list[child1][1], list[child2][1]) == 1 ? child1 : child2;
    }
}
void process(int V, int start, int minList[]){
    int now, min;
    int check[V+MARGIN];
    int minHeap[V+MARGIN][2], end = -1;
    Node *node;
    int i;

    for(i = 0;i <= V;i++){
        check[i] = 0;
    }
    minList[start] = 0;
    minHeap[++end][0] = start;
    minHeap[end][1] = minList[start];

    now = start;
    while(end > -1){

        now = minHeap[0][0];
        minHeap[0][0] = minHeap[end][0];
        minHeap[0][1] = minHeap[end--][1];
        if(end > -1)
            reheapDown(minHeap, end);
            
        if(check[now] == 1)
            continue;
        check[now] = 1;

        node = Adjacent[now];
        while(node != NULL){
            i = node->data[0];

            if(check[i] == 0){
                if(compare(minList[now]+(node->data[1]), minList[i]) == 1){
                    minList[i] = minList[now]+(node->data[1]);

                    minHeap[++end][0] = i;
                    minHeap[end][1] = minList[i];
                    reheapUp(minHeap, end);
                }
            }

            node = node->next;
        }

    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C] 어찌저찌 통과는 했는데... 궁금한점이 있습니다.

irsam78 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말