글 읽기 - HEAP을 직접 구현해서 풀어봤습니다. 로직이 틀린건가요?

pok_winter 3년 전 0

HEAP, Linked List를 직접 구현했습니다.

제가 쓴 로직은 아래와 같습니다.

visited[20100]에 각 정점에 따른 최소 비용을 집어넣는다.

여기서 집어 넣는 방법은 BFS + Priority Queue를 이용해서 최소 비용만을 이용하여 visited[20100]에 저장한다. ( push() 함수 제일 처음에 적용합니다)

이렇게 수행하는게 틀렸는지 시간 초과가 뜨는데, 링크드리스트 / 힙을 썼는데 왜 시간 초과가 나는지 의문입니다.

혹시 우선 순위 큐 + BFS와 다익스트라의 차이가 큰 건가요?? 다익스트라가 우선 순위 큐를 이용한거라 들어서 본 방법이 다익스트라로 알고 있는데 말이죠..

아시는 분 계시면 도와주시면 감사하겠습니다.

#include <stdio.h>

int N, M, S, u, v, w;

int arr_idx, hrr_idx;

struct NODE {
	int name;
	int val;
	NODE* next;
} arr[20100];

NODE* arr_alloc() {
	return &arr[arr_idx++];
}

struct HODE {
	int name;
	int cnt;
} hrr[300100];

HODE* hrr_alloc() {
	return &hrr[hrr_idx++];
}

NODE* map[20100];
HODE* HEAP[300100];
int ptr;
int visited[20100];

int intncmp(int n1, int n2) {
	return n1 < n2 ? 1 : 0;
}

void push(int name, int cnt) {
	if (visited[name] <= cnt) return;
	else visited[name] = cnt;
	HODE* cur = hrr_alloc();
	cur->name = name;
	cur->cnt = cnt;

	HEAP[++ptr] = cur;
	int c = ptr, p = c / 2;

	while (p >= 1) {
		if (intncmp(HEAP[c]->cnt, HEAP[p]->cnt)) {
			HODE* tmp = HEAP[c];
			HEAP[c] = HEAP[p];
			HEAP[p] = tmp;

			c = p, p = c / 2;
		}
		else break;
	}
	return;
}

HODE* pop() {
	HODE* val = HEAP[1];

	HEAP[1] = HEAP[ptr--];

	int p = 1, l = 2, r = 3, c;

	while (l <= ptr) {
		if (r > ptr) c = l;
		else {
			if (intncmp(HEAP[l]->cnt, HEAP[r]->cnt)) c = l;
			else c = r;
		}

		if (intncmp(HEAP[p]->cnt, HEAP[c]->cnt)) {
			HODE* tmp = HEAP[c];
			HEAP[c] = HEAP[p];
			HEAP[p] = tmp;

			p = c; l = p * 2; r = l + 1;
		}
		else break;
	}

	return val;
}

void init() {
	scanf("%d %d", &N, &M);
	scanf("%d", &S);

	for (int m = 0; m < M; ++m) {
		scanf("%d %d %d", &u, &v, &w);

		NODE* tmp = arr_alloc();
		tmp->name = v;
		tmp->val = w;

		if (map[u]) {
			tmp->next = map[u];
			map[u] = tmp;
		}
		else {
			map[u] = tmp;
		}
	}

	for (int n = 1; n <= N; ++n) {
		visited[n] = 100000000;
	}
}

void BFS() {
	push(S, 0);

	while (ptr > 0) {
		HODE* now = pop();

		int s = now->name;
		int c = now->cnt;

		NODE* nxt = map[s];
		while (nxt) {
			push(nxt->name, nxt->val + c);
			nxt = nxt->next;
		}
	}
}

int main(void) {
	// freopen("input.txt", "r", stdin);

	init();

	BFS();

	for (int n = 1; n <= N; ++n) {
		if (visited[n] == 100000000) printf("INF\n");
		else printf("%d\n", visited[n]);
	}
}

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

문제

문제

출처

ICPC

HEAP을 직접 구현해서 풀어봤습니다. 로직이 틀린건가요?

pok_winter 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말