D (Dijkstra Algorithm) 구현 질의

su1885 Reply 5 years 17 weeks ago
안녕하세요. 과제에 명시된대로 일체의 외부 라이브러리를 사용하지 않고 C의 기본 기능만을 이용해 다익스트라 알고리즘을 작성하고 있습니다. 그런데 일부 케이스에 대해서, WA가 발생하는 것을 볼 수 있었습니다. 이 원인에 대해서 알고 싶습니다. 이하는 제가 사용한 코드입니다. #include <stdio.h> #include <stdlib.h> #define INF 10e8 typedef struct _V { int to[1100]; int w[1100]; int p; int d; int n; char s[110]; }; typedef struct _V V; V *pq[2010], G[2010]; int dist[20100], addr[20100]; int pq_size, map_size, v, e, tp; char str[1010], *loc, map[20100][20]; int cmp_str(char *s1, char *s2) { for(int i = 0; ; i++) { if(s1[i] < s2[i]) return -1; else if(s1[i] > s2[i]) return 1; if(!s1[i] && !s2[i]) break; } return 0; } void map_str(char *s1) { int i; for(i = 0; s1[i]; i++) map[map_size][i] = s1[i]; map[map_size][i] = 0; map_size++; } int map_find(char *s1) { for(int i = 0; i < map_size; i++) { if(!cmp_str(map[i], s1)) return i; } return -1; } void ex_v(int x, int y) { V *tmp; int taddr; taddr = addr[pq[x]->n]; addr[pq[x]->n] = addr[pq[y]->n]; addr[pq[y]->n] = taddr; tmp = pq[x]; pq[x] = pq[y]; pq[y] = tmp; } void min_heapify(int k) { int l = k * 2; int r = k * 2 + 1; int min; if(l <= pq_size && pq[l]->d < pq[k]->d) min = l; else if(l <= pq_size && pq[l]->d == pq[k]->d && cmp_str(pq[l]->s, pq[k]->s) < 0) min = l; else min = k; if(r <= pq_size && pq[r]->d < pq[min]->d) min = r; else if(r <= pq_size && pq[r]->d == pq[min]->d && cmp_str(pq[r]->s, pq[min]->s) < 0) min = r; else min = min; if(min != k) { ex_v(min, k); min_heapify(min); } } V *pq_extract_min() { V *tmp = pq[1]; pq[1] = pq[pq_size]; pq_size--; min_heapify(1); return tmp; } void pq_dec_key(int pos, int key) { int i = addr[pos]; pq[i]->d = key; while(i > 1 && pq[i / 2]->d >= pq[i]->d) { if(pq[i / 2]->d == pq[i]->d && cmp_str(pq[i / 2]->s, pq[i]->s) < 0) break; ex_v(i / 2, i); i /= 2; } } void push_back(V *v, int i, int k) { v->to[v->p] = i; v->w[v->p] = k; v->p += 1; } void pq_build() { for(int i = pq_size / 2; i > 0; i--) min_heapify(i); } int main() { pq_size = 1; map_size = 0; scanf("%s", str); scanf("%d", &e); loc = str; for(int i = 0; str[i]; i++) if(str[i] == ',') pq_size++, str[i] = 0; v = pq_size; for(int i = 0; i < pq_size; i++) { V *telem = &G[i]; for(int j = 0; j < 110; j++) { telem->to[j] = 0; telem->w[j] = 0; } telem->p = 0; telem->d = INF; telem->n = i; int pos = 0; while(*loc) telem->s[pos++] = *loc, loc++; telem->s[pos] = 0; map_str(telem->s); loc++; // printf("%s\n", telem->s); pq[i + 1] = telem; addr[i] = i + 1; dist[i] = INF; } pq_build(); for(int i = 0; i < e; i++) { scanf("%s", str); char *lp[3]; lp[0] = str; int tp = 1; for(int j = 0; str[j]; j++) { if(str[j] == ',') lp[tp++] = &str[j + 1], str[j] = 0; } int st, ed; st = map_find(lp[0]); ed = map_find(lp[1]); int tmp = 0; for(char *j = lp[2]; *j; j++) { tmp *= 10; tmp += (*j) - '0'; } // printf("%d -> %d, w: %d\n", st, ed, tmp); push_back(&G[st], ed, tmp); } /* for(int i = 0; i < v; i++) { for(int j = 0; j < G[i].p; j++) { printf("%d -> %d, %d\n", i, G[i].to[j], G[i].w[j]); } } */ pq_dec_key(0, 0); dist[0] = 0; while(pq_size != 0) { int cur = pq_extract_min()->n; for(int i = 0; i < G[cur].p; i++) { if(dist[G[cur].to[i]] > dist[cur] + G[cur].w[i]) { dist[G[cur].to[i]] = dist[cur] + G[cur].w[i]; pq_dec_key(G[cur].to[i], dist[G[cur].to[i]]); } } } for(int i = 0; i < v; i++) { printf("%d", dist[i]); if(i != v - 1) putchar('\n'); } } PS. Input 형식이 타 저지 사이트의 유사 문제에 비해서 많이 까다롭네요... PS2. V, E의 범위에 대한 내용도 추가해주셨으면 좋겠습니다. PS3. Vertex들의 이름이 한 글자가 아닌 문자열이 올 수도 있는 것인지 확신을 얻고 싶습니다.
su1885 Reply 5 years 17 weeks ago
해결했습니다!
Hyunwoo Reply 5 years 17 weeks ago
축하합니다.
su1885 Reply 5 years 17 weeks ago
질문에 첨부된 소스코드를 삭제해주실 수 있는지 여쭤보고 싶습니다.