글 읽기 - (C)하루종일 이 문제 끙끙 싸맸는데 답이 안나오네요 코딩 질문드립니다. ㅠㅠ

flxl765 5년 전 0

최소 히프로 가중치가 적은 순서대로 정렬하도록 썼구요

while(H->heap_size != 0) 문에서 최단 거리 설정해주고

나름 신경써서 코딩했는데 출력값은

INF

이렇게밖에 안떠서 멘붕왔네요;; 거의 하루종일 싸맸는데...하...

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <memory.h>

#pragma warning(disable:4996)

#define INF 77777
#define MAX_VERTICES 20001
#define MAX_SIZE 20001

typedef struct{
	int index;
	int dist;
}element;


typedef struct {
	element heap[MAX_SIZE];
	int heap_size;
}HeapType;

/*그래프 인접 행렬*/
typedef struct GraphType {
	int adj_mat[MAX_SIZE][MAX_SIZE];
	int wei_mat[MAX_SIZE][MAX_SIZE];
}GraphType;

/*히프 트리 함수*/
void heap_init(HeapType *h){
	h->heap_size = 0;
}

void insert_minHeap(HeapType *h, element item)
{
	int i;
	i = ++(h->heap_size);

	while ((i != 1) && (item.dist < h->heap[i / 2].dist)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;
}

element delete_minHeap(HeapType *h)
{
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = parent * 2;

	while (child <= h->heap_size) {
		if (child < h->heap_size && (h->heap[child]).dist > h->heap[child + 1].dist)
			child++;
		if (temp.dist <= h->heap[child].dist) break;
		h->heap[parent] = h->heap[child];
		parent = child;
		child = parent * 2;
	}
	h->heap[parent] = temp;
	return item;
}

void element_init(element *e)
{
	e->dist = 0;
	e->index = 0;
}

void graph_init(GraphType *g,int ind)
{
	int r, c;
	for (r = 1; r <= ind ; r++)
		for (c = 1; c <= ind; c++){
			g->adj_mat[r][c] = 0;
			g->wei_mat[r][c] = 0;
		}
}

void insert_edge(GraphType *g, int start, int end, int w, int ind){
	if (start > ind || end > ind) {
		return;
	}
	g->adj_mat[start][end] = 1;
	g->wei_mat[start][end] = w;
}


int main()
{
	int ind, en, str, i, r, j;
	scanf("%d %d", &ind, &en);
	scanf("%d", &str);

	HeapType *H = (HeapType*)malloc(sizeof(HeapType));
	heap_init(H);
	GraphType *g = (GraphType*)malloc(sizeof(GraphType));
	graph_init(g ,ind);

	element *eq = (element*)malloc(sizeof(element) * 20000); 				//최소 거리 넣는 element타입 배열
	element cur;							//방문 후 가중치 최소인 다음 접전 꺼내쓸 element
	element ein;							//파라미터 삽입용 element

	for (i = 1; i <= ind; i++){					//정점 수만큼 element에 가중치 넣기
		if (i == str){								//출발점에 시작값 0, 나머지는 INF 넣기
			eq[i].dist = 0;
			eq[i].index = i;
		}
		else {
			eq[i].dist = INF;
			eq[i].index = i;
		}
	}
	for (r = 1; r <= ind; r++) {
		ein = eq[r];
		insert_minHeap(H, ein);
	}
	int st, ed, w;
	for (int k = 0; k < en; k++){				//간선과 가중치 그래프타입에 넣기
		scanf("%d %d %d", &st, &ed, &w);
		insert_edge(g, st, en, w, ind);
	}
	while (H->heap_size != 0) {
		cur = delete_minHeap(H);
		for (j = 1; j <= ind; j++) {
			if (g->adj_mat[cur.index][j] == 1) {

				if (eq[j].dist > (cur.dist + g->wei_mat[cur.index][j]))  {
					eq[j].dist = (cur.dist + g->wei_mat[cur.index][j]);		//최소 거리 삽입
					ein = eq[j];
					insert_minHeap(H, ein);
				}
			}
		}
	}
	for (int k = 1; k <= ind; k++){
		(eq[k].dist == INF) ? printf("INF\n") : printf("%d\n", eq[r].dist);
	}
	free(eq);
}

vl0612 5년 전 0

댓글 쓰고 오류가 있어서 고치려고 했더니 수정이 안되네요 또르륵... 이건 건의해봐야겠습니다..

vl0612 5년 전 0

일단 고쳐보았습니다.

제가 ->이런 거나 *이런거나 malloc pragma 하나도 모르는 사람인지라ㅋㅋㅋ 대충 코드눈치보며 고쳐보았습니다.

틀린 부분 및 없어도 되는 군더더기(당장 이 코드에서 없어도(주석처리해도) 돌아가는 부분만) 대강 표기해두었습니다.

Heap 자료구조를 직접 만들어쓰다니......ㄷㄷ 자료구조를 직접 구현할 수 있다는 점은 매우 존경스럽지만, 알고리즘 공부를 위해서라면 C++ 쓰는 것을 추천합니다.

C++에서는 priority_queue 라고 개발자들이 제공하는 훌륭한 STL이 제공됩니다. 문법 쪼끔만 공부하면 돼요.

동적배열도 stl에 있는 vector로 간단히 선언 및 여러 유용한 사용이 가능합니다

저런 어려운 문법과 자료구조 구현이 실제 프로그래밍 할 때는 도움되겠지만, 지속적이고 편안한(?) 알고리즘 공부를 위해서는 좀 더 경량화된 문법 등을 사용하는게 편리하다고 생각합니다. (본인이 문법을 못 읽어서 하는 찡얼거림 맞습니다 ㅋㅋㅋ)

그리고 아래와 같이 고치면 당장 예제는 돌아가지만

제출 결과 테스트케이스에 대해서는 <메모리초과>가 나옵니다. 추가 댓글로 피드백하겠습니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <memory.h> 

#pragma warning(disable:4996) //우왕 신기해요 첨 보는 문법 

#define INF 77777
#define MAX_VERTICES 20001
#define MAX_SIZE 20001

typedef struct{  
	int index;
	int dist;
}element;


typedef struct {
	element heap[MAX_SIZE];
	int heap_size;
}HeapType;

/*그래프 인접 행렬*/
typedef struct GraphType { //그냥 전역 변수로 선언하면 편할텐데요... ... 
	int adj_mat[MAX_SIZE][MAX_SIZE]; 
	int wei_mat[MAX_SIZE][MAX_SIZE];
}GraphType;

/*히프 트리 함수*/
//직접 짜지 말구 알고리즘 대회에서는 stl의 priority_queue!
// c++를 배우면 몸과 마음과 머리와 손이 편합니다.
//코드를 보면서 느낀 점은 이건 다익스트라 코드인가요 아니면 자료구조 힙을 구현하는 문제인가요 ㄷㄷㄷ
void heap_init(HeapType *h){
	h->heap_size = 0;
}

void insert_minHeap(HeapType *h, element item)
{
	int i;
	i = ++(h->heap_size);

	while ((i != 1) && (item.dist < h->heap[i / 2].dist)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;
}

element delete_minHeap(HeapType *h)
{
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = parent * 2;

	while (child <= h->heap_size) {
		if (child < h->heap_size && (h->heap[child]).dist > h->heap[child + 1].dist)
			child++;
		if (temp.dist <= h->heap[child].dist) break;
		h->heap[parent] = h->heap[child];
		parent = child;
		child = parent * 2;
	}
	h->heap[parent] = temp;
	return item;
}

void element_init(element *e) 
{
	e->dist = 0;
	e->index = 0;
}

void graph_init(GraphType *g,int ind)
{
	int r, c;
	for (r = 1; r <= ind ; r++)
		for (c = 1; c <= ind; c++){
			//g->adj_mat[r][c] = INF; 군더더기 
			g->wei_mat[r][c] = INF; //제가 문법을 잘 모르므로 이부분 피드백은  생략.. 
		}
}

void insert_edge(GraphType *g, int start, int end, int w, int ind){ 
	//if (start > ind || end > ind) { 군더더기. 없어도 됩니다. 
	//	return;군더더기 
	//} 군더더기 
	//g->adj_mat[start][end] = 1; 군더더기 
	g->wei_mat[start][end] = w;
}


int main()
{
	int ind, en, str, i, r, j;
	scanf("%d %d", &ind, &en);
	scanf("%d", &str);

	HeapType *H = (HeapType*)malloc(sizeof(HeapType));
	heap_init(H); 
	GraphType *g = (GraphType*)malloc(sizeof(GraphType));
	graph_init(g ,ind);

	element *eq = (element*)malloc(sizeof(element) * 20000); 				//최소 거리 넣는 element타입 배열
	element cur;							//방문 후 가중치 최소인 다음 접전 꺼내쓸 element
	element ein;							//파라미터 삽입용 element

	for (i = 1; i <= ind; i++){					//정점 수만큼 element에 가중치 넣기
		if (i == str){								//출발점에 시작값 0, 나머지는 INF 넣기
			eq[i].dist = 0;
			eq[i].index = i;
		}
		else {
			eq[i].dist = INF;
			eq[i].index = i;
		}
	}
	for (r = 1; r <= ind; r++) {
		ein = eq[r];
		insert_minHeap(H, ein);
	}
	int st, ed, w;
	for (int k = 0; k < en; k++){				//간선과 가중치 그래프타입에 넣기
		scanf("%d %d %d", &st, &ed, &w);
		insert_edge(g, st, ed, w, ind); //오타 있었죠? en이 아니고 ed입니다. 
	}
	while (H->heap_size != 0) {
		cur = delete_minHeap(H);
		for (j = 1; j <= ind; j++) {
			//if (g->adj_mat[cur.index][j] == 1) { //코드구현 방식에 따라 다르겠지만 아마도 군더더기일 확률 높습니다. 
				if (eq[j].dist > (cur.dist + g->wei_mat[cur.index][j]))  {
					eq[j].dist = (cur.dist + g->wei_mat[cur.index][j]);		//최소 거리 삽입
					//ein = eq[j]; 왜 이렇게? 그냥 바로 넣어두 됩니다. 
					insert_minHeap(H, eq[j]); //ein을 eq[j]로 바꿈 
				}
			//}
		}
	}
	for (int k = 1; k <= ind; k++){
		(eq[k].dist == INF) ? printf("INF\n") : printf("%d\n", eq[k].dist); //r이 아니고 k 
	}
	free(eq);
}

vl0612 5년 전 0

일단, (문법도 모르면서 대충 읽어보기에) 코드의 흐름 자체는 틀린 점이 없습니다. 솔직히 해당문법에서 군더더기도 adj_mat관려된 부분밖에 없다는 점에서 (저보다 훨씬(...)) 훌륭합니다.

메모리 초과가 나는 원인

<그래프를 나타내는 방식에는 인접행렬과 인접리스트 방식이 있습니다.

그리고 위의 코드에서 사용한 방식은 아마 인접행렬로 추정되고

20000*20000 짜리 배열이 만들어지니까 메모리 가볍게 초과...

인접리스트를 사용하면 간선 개수에 비례하여 메모리를 먹으므로 30만개 정도면 굉장히 여유롭게 메모리를 사용할 수 있습니다. (128mb면 수천만개 int배열 선언이 가능하니까요)

"결론 : 지우고 다시 짜는게 편합니다."

나아가 알고리즘 대회를 위한 간단한 두가지 피드백을 드리자면

전역변수 활용을 생활화 합시다.

실무관련 프로그래밍 혹은 자바 쓰시는 분들은 지역변수를 주고 받고 하는 것을 사랑한다고 들었지만

알고리즘 대회에서 전역변수를 사용하면 시간적으로두, 혹은 코드의 쾌적함을 위해서라두 정말로 얻을 수 있는 점이 많습니다.

2. C++를 사용합시다 C++에 STL을 생활화합시다.

자료구조를 직접 구현할 수 있다는 점은 매우 존경스럽지만, 알고리즘 공부를 위해서라면 C++ 쓰는 것을 추천합니다.

C++에서는 priority_queue 라고 개발자들이 제공하는 훌륭한 STL이 제공됩니다. 문법 쪼끔만 공부하면 돼요.

동적배열도 stl에 있는 vector로 간단히 선언 및 여러 유용한 사용이 가능합니다

저런 어려운 문법과 자료구조 구현이 실제 프로그래밍 할 때는 도움되겠지만, 지속적이고 편안한(?) 알고리즘 공부를 위해서는 좀 더 경량화된 문법 등을 사용하는게 편리하다고 생각합니다.

(본인이 문법을 못 읽어서 하는 찡얼거림 맞습니다 ㅋㅋㅋ)

조언으로

printf함수는 어느 부분에서 문제가 일어났는지 파악할 때 용이합니다.

아무 코드 중간에 printf("Hello World");를 삽입한 뒤 헬로 월드가 출력 여부에 따라 그 부분이 실행되었음을 볼 수 있습니다.

요약하자면

C++를 공부합시다
C++의 priority_queue와 vector를 익힙시다.
전역변수 활용을 생활화 합시다.
문법 공부 ㄱㄱ
솔직히 코딩 실력은 저보다 좋아보입니다. 따라서 저는 이제 짜지겠습니다 쭈그리쭈그리

쭈그리짜그리 짜지기 전에

제 C++코드 하나를 주서고가 함께 첨부하고 사라지겠습니다.

예전에 짰던 거를 지금 살짝 군더더기만 제거한거라 변수명이 미쳐 날뛰고 있지만 (+군더더기가 눈에 계속 거슬리지만 치우면 치울수록 하나씩 계속 보이므로 그냥 하나만 냅두겠습니다............흑흑

그래도 이정도면 가장 일반적인 형태의 C++ ElgV dij코드가 아닐까 싶습니다.

#include<cstdio>
#include<vector>
#include<queue>
//위에 세 줄을 bit/stdc++.h를 인클루드 함으로 줄일 수 있음
#define INF 987654321 
using namespace std;
int n,m,start,a,b,c,i,j,k; //전역변수 넘나 좋은 것
struct st{int fin; int cost;}imsi;
vector <st> edge[30001]; //동적 배열이랑 인접리스트 비스므리 한 거 입니다. 알고리즘 대회를 위해서는 malloc 대신 vector와 친해지세요
int minDis[30001]; //전역변수로 배열을 선언하면 전부 0으로 초기화되어있습니다.
struct cmp{
	bool operator()(st a,st b){
	return a.cost>b.cost;}
}; //이건 priority_queue를 사용하기 위한 오퍼레이터
priority_queue <st,vector<st>,cmp> pq; 
void dij(){ //메인에 함께 넣어두 됩니다. 아래 여섯 줄 암기 혹은 <자연스러워질 때까지 코딩해서 체화>
	while(!pq.empty()){ //힙이 빌 때까지 돌아가는 와일문 하나
		imsi=pq.top();	pq.pop(); //힙에서 하나 빼고
		for(i=0;i<edge[imsi.fin].size();i++) //간선들 도는 포문 하나
		{
			if(imsi.cost+edge[imsi.fin][i].cost<minDis[edge[imsi.fin][i].fin]) //갱신 판단하는 이프문 하나
			{
				minDis[edge[imsi.fin][i].fin]=imsi.cost+edge[imsi.fin][i].cost; //갱
				pq.push((st){edge[imsi.fin][i].fin,imsi.cost+edge[imsi.fin][i].cost}); //갱신되면 다시 힙에 밀어넣습니다.
			}
		}
		
	}
}
int main(void)
{
	scanf("%d %d",&n,&m); //입력받기
	scanf("%d",&start);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&a,&b,&c);
		edge[a].push_back((st){b,c});
	} //열심히 입력받기
	for(i=1;i<=n;i++) minDis[i]=INF; //전역변수인 배열은 0으로 초기화 되어있으니까 다시 열심히 INF로 초기화
	minDis[start]=0; //시작값은 0
	for(i=1;i<=n;i++) pq.push((st){i,minDis[i]}); //아까 말한 군더더기...pq에 적절한 초기값(아마 시작점,cost=0으로 st)을 넣음으로 간단히 지울 수 있습니다...ㅇㅁㅇ..
	dij();
	for(i=1;i<=n;i++)
	{
		if(minDis[i]==INF) printf("INF\n");
		else printf("%d\n",minDis[i]);
	}//출력
	return 0;
}

vl0612 5년 전 0

아 마지막으로 틀린 이유 요약

INFINFINF가 뜨는 이유는 오지게 많은 오타 (코드에 주석으로 피드백했습니다)

2.결정적으로 인접리스트 방식이 아닌 인접행렬로 구현하여 메모리초과

그러합니다.

솔직히 이 상황에선 인접리스트를 인접행렬로 바꿔끼우는 것보다 <지우고 다시>가 더 공부도 되고 훨씬 편합니다...

flxl765 5년 전 0

흠.. 그렇군요 결국 인접리스트로 구현해야만 하는거군요...

제가 아직 초짜라 인접리스트는 뭔가 구현하기 어려워서 행렬방식으로 어떻게 할 수 없을까 했는데 메모리 오류라 ㅠㅠ

C 자료구조 배운지 반년정도밖에 안되가지고 C++은 아직 시작조차 못한 상황이라 C로 문제를 풀 수 없을까 해서 글을 올려봤습니다.

많은 도움이 된거 같아요 감사해요 ^^

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

문제

문제

출처

ICPC

(C)하루종일 이 문제 끙끙 싸맸는데 답이 안나오네요 코딩 질문드립니다. ㅠㅠ

flxl765 5년 전 0

vl0612 5년 전 0

vl0612 5년 전 0

vl0612 5년 전 0

vl0612 5년 전 0

flxl765 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말