floyd 알고리즘
중독된
질문 내용 :
#include stdio.h
#include limits.h
#include stdlib.h
#include memory.h
typedef struct graph{
int no1;
int no2;
int dis;
}graph;
void floyd(int n, int cnt)
{
file *fp;
int **a, **weight;
int i, j, k;
graph temp;
fp = fopen(data.txt, r);
if(fp == null){
printf(파일 개방 실패!!!\n);
return;
}
weight = (int**)malloc(n * sizeof(*weight)); //2차원 배열 동적 할당
for(i = 0; i n; i++){
weight[i] = (int*)malloc(n * sizeof(**weight));
}
a = (int**)malloc(n * sizeof(*a)); //2차원 배열 동적 할당
for(i = 0; i n; i++){
a[i] = (int*)malloc(n * sizeof(**a));
}
for(i = 0; i n; i++){ //0으로 초기화
for(j = 0; j n; j++){
a[i][j] = 0;
weight[i][j] = 0;
}
}
for(i = 0; i cnt; i++){ //입력 부분
fscanf(fp, %d%d%d, &temp.no1, &temp.no2, &temp.dis);
weight[temp.no1][temp.no2] = temp.dis;
}
rewind(fp);
for(i = 0; i n; i++){ //배열 출력 부분
for(j = 0; j n; j++){
printf(%-4d, weight[i][j]);
}
printf(\n);
}
for(i = 0; i n; i++){ //a배열에 weight 배열을 덮어 씌움
for(j = 0; j n; j++){
a[i][j] = weight[i][j];
}
}
//
printf(\n\n); //확인
for(i = 0; i n; i++){
for(j = 0; j n; j++){
printf(%-4d, a[i][j]);
}
printf(\n);
}
//
for(k = 0; k n; k++){
for(i = 0; i n; i++){
for(j = 0; j n; j++){
if(a[i][k] + a[k][j] a[i][j]){
a[i][j] = a[i][k] + a[k][j];
}
}
}
}printf(\n\n); //확인
for(i = 0; i n; i++){
for(j = 0; j n; j++){
printf(%-4d, a[i][j]);
}
printf(\n);
}
printf(\n);
for(i = 0; i n; i++){ //메모리 동적할당 해제
free(weight[i]);
free(a[i]);
}
free(weight);
free(a);//여기까지
fclose(fp);
}
int main()
{
file *fp;
int max = 0;
graph temp;
int cnt = 0;
int i = 0, j = 0;
fp = fopen(data.txt, r);
if(fp == null){
printf(파일 개방 실패!!!\n);
return 0;
}
while(!feof(fp)){ //갯수 파악 및 최고 vertex 파악
fscanf(fp, %d%d%d, &temp.no1, &temp.no2, &temp.dis);
cnt++;
if(max temp.no1){
max = temp.no1;
}
if(max temp.no2){
max = temp.no2;
}
}
rewind(fp);
max += 1;
floyd(max, cnt);
fclose(fp);
return 0;
}/*************************************************************************
아무리 봐도 잘 모르겠어서 다시 질문 드립니다.
위에 빨갛게 해놓은 부분이 문제인데....
메인함수는 문서를 읽어들어 거기에 저장된 vertex의 최대값을 알아내고
기록되어있는 자료가 몇갠지 갯수를 파악하고 함수를 호출하고...
함수로 들어가면 다시 파일을 오픈하고 넘겨받은 매개인자 값으로 메모리를 동적할당합니다.
2차원 배열루요 그리고 weight 배열에 오픈한 파일에 들어있는 값을 집어 넣습니다.(파란색)
메모장에는 0 1 12 // 0 2 21이런 식으로 저장되어 있구요 //는 구분하기 위해 제가 임의로 한거고
그냥 엔터로 구분되어 있습니다. 앞에 숫자 2개는 vertex 넘버구요... 3번째 값은 앞의 2개 vertex에
대한 값입니다. 즉 0 1의 값은 12이고 0 2의 값은 21이 됩니다. 0에서 1로 가는데는 12만큼의 거리이고
0에서 2로 가는데는 21만큼의21만큼의 거리입니다.
그리고 밑에 출력은 제대로 입력이 되어 있는지 확인하기 위해 출력해 보는 것이고
그 바로 아래에는 weight배열에 입력되어 있는 값을 a배열에 복사합니다.
그리고 a배열에 제대로 복사 되었는지 다시 확인...
그리고 빨간색 부분인 floyd 알고리즘인데... 책 보고 그대로 타이핑한거고 다른 문제에서는
제대로 됐는데 이 문제에서는 안되네요... 아무튼 floyd 알고리즘을 지나고 나면 배열 a가
0으로 초기화 되버립니다.
배열 a에는 분명히 weight배열이 복사되었는데... 어째서 floyd 알고리즘만 지나면
초기화된 값이 출력이 되는지 모르겠습니다. ㅠ.ㅠ
*****************************************************************************/
