글 읽기 - [C] 2623 위상정렬 런타임 에러

so4644009 4년 전 0

큐를 만들고 큐가 비어있으면 0을 출력하고 프로그램을 종료하고, 아니면 큐에 있는 값을 pop해서 위상 정렬을 실행하는 걸로 했는데 계속 런타임 에러가 나오네요 혹시 어느 부분이 잘못됐는지 봐주실수 있나요 문제테스트케이스나 질문 게시판에 있는 중복 간선 케이스(ex. 2 2 2 1 2 2 1 2가 입력됐을 때) 모두 바르게 출력됐습니다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX 1001

bool graph[MAX][MAX];
int check[MAX];
int result[MAX];
typedef struct queue {
	int item;
	struct queue* ptr;
}q;
q* front = NULL;
q* rear = NULL;
void push(const int);
int pop();
int isEmpty();

int main(void) {
	int n, m, input_number, before, input;
	int index = 0;
	int edge;
	scanf("%d %d", &n, &m);
	while (m--) {
		scanf("%d %d", &input_number, &before);
		while (--input_number) {
			scanf("%d", &input);
			if (!graph[before][input]) { //중복 간선을 걸러주는 if문
				graph[before][input] = true;
				++check[input];
				before = input;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (!check[i]) {
			push(i); //부모 노드의 개수가 0일때 큐에 push
		}
	}

	for (int i = 0; i < n; ++i) {
		if (isEmpty()) { //비어있으면 0을 출력하고 프로그램 종료 
			puts("0");
			return 0;
		}
		else {
			edge = pop();
			result[index++] = edge;
			for (int j = 1; j <= n; ++j) {
				if (graph[edge][j]) {
					--check[j];
					if (!check[j]) {
						push(j);
					}
				}
			}
		}

	}
	for (int i = 0; i < n; ++i) printf("%d\n", result[i]);
	return 0;
}

int isEmpty() {
	return rear == NULL;
}

int pop() {
	int item;
	q* tmp = malloc(sizeof(q));
	tmp = front;
	front = tmp->ptr;
	item = tmp->item;
	free(tmp);
	return item;
}

void push(const int item) {
	q* node = malloc(sizeof(q));
	node->item = item;
	node->ptr = NULL;
	if (!front) {
		front = node;
		rear = node;
	}
	else {
		rear->ptr = node;
		rear = node;
	}
	return;
}

dlwocks31 4년 전 1

마지막으로 남아있는 원소가 pop될때 rear가 null로 설정되지 않아 empty로 판정되지 않는거 같아요.

dlwocks31 4년 전 1

그걸 고쳐도 틀리긴 하는데, 왜냐하면 중복된 간선을 제거하면서 무시한 선후관계가 생겨요.

2
2 3
2 3 1

so4644009 4년 전 0

감사합니다!

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

문제

문제

출처

ICPC

[C] 2623 위상정렬 런타임 에러

so4644009 4년 전 0

dlwocks31 4년 전 1

dlwocks31 4년 전 1

so4644009 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말