다익스트라입니다 ㅠ

#1 
#include <stdio.h>
#include <stdlib.h>

#define N 6
#define INF 9999

int flag[N + 1];
int dist[N + 1];

int i, j, min, position;

int data[N + 1][N + 1] = {
	{0, 0, 0, 0, 0, 0, 0},
{0, 0, 2,INF, 3,INF,INF},
{0,INF, 0, 4 , 1, 7,INF},
{0,INF,INF, 0, 4, 1, 3},
{0,INF, 2, 2, 0, 1,INF},
{0,INF,INF, 1,INF, 0, 6},
{0,INF, 3,INF, 8,INF, 0}
};


void main()
{
	for (i = 1; i <= N; i++) {
		flag[i] = 0;
		dist[i] = INF;
	}

	dist[1] = 0;

	for (i = 1; i <= N; i++) {
		min = INF;
		for (j = 1; j <= N; j++) {
			if (min > dist[i] && flag[j] == 0) {
				min = dist[i] + data[i][j];
				position = j;
			}
		}
		flag[position] = 1;

		for (j = 1; j <= N; j++) {
			if (dist[j] > data[position][j] + dist[position] && data[position][j] != INF) {
				dist[j] = data[position][j] + dist[position];
			}
		}
	}

	for (i = 1; i <= N; i++) {
		printf("1 ~ %d : %d \n", i, dist[i]);
	}
}

이코드 값이4 이거고
이거에서
5 이대로 수정을 하고
(설정한 변수같은거 안바꾸고 가르쳐주셔야되요 ㅠ 말그대로 전과해서 뉴비에요…)
그리고

6
6.PNG769×485 71.3 KB

1~6까지 최단거리는 9로 출력되어있는데 1 4 3 6경로의 가중치의합은 8인데 결과가 9로 출력된 이유가궁금하네요 ㅠ 다시8로 올바르게 출력되도록 하는 코드가 있을까요

#2

동일한 질문글 아닌가요? std::vector의 사용법은 네이버나 구글에서 검색해도 쉽게 알 수 있습니다.

#3

원리적인 부분은 이전 토픽에 달린 여러 답변에서 충분히 답변이 되었다고 생각 됩니다.

아니면, 질문자님은 현재 코드에서 큰 변경 없이 경로를 출력하는 코드를 원하시는건가요?

#4

열심히 공부하겠습니다 ㅠ

#5

네네 큰변경없이 경로 출력하는거 맞아요. 그리고 위에 코드로는 1~6이 9가나오는데 제대로 코드를짜면 8이나온다고 하더라구요…
그이유도 궁금하네요…

#6 
#include <stdio.h>
#include <stdlib.h>

#define N 6
#define INF 9999

int flag[N + 1];
int dist[N + 1];
int index[N + 1];

int i, j, min, position;

int data[N + 1][N + 1] = {
   {0, 0, 0, 0, 0, 0, 0},
{0, 0, 2,INF, 3,INF,INF},
{0,INF, 0, 4 , 1, 7,INF},
{0,INF,INF, 0, 4, 1, 3},
{0,INF, 2, 2, 0, 1,INF},
{0,INF,INF, 1,INF, 0, 6},
{0,INF, 3,INF, 8,INF, 0}
};



int main()
{
   for (int i = 1; i <= N; i++) {
      flag[i] = 0;
      dist[i] = INF;
   }

   dist[1] = 0;

   for (int i = 1; i <= N; i++) {
      min = INF;
      for (int i = 1; i <= N; i++) {
         if (min > dist[i] && flag[i] == 0) {
            min = dist[i] + data[i][j];
            position = i;
         }
      }
      flag[position] = 1;
      for (int j = 1; j <= N; j++) {
         if (dist[j] > dist[position] + data[position][j] && data[position][j] != INF) {
            dist[j] = dist[position] + data[position][j];
            index[j] = position;
         }
      }
   }
   for (int i = 1; i <= N; i++) {
      printf("1 ~ %d : %d Path: %d", i, dist[i], i);
      position = i;
      do {
         printf(" <- %d", index[position]);
         position = index[position];
      } while (index[position]);
      puts("");
   }

}

제 나름대로해봤는데 이렇게됬어요! 근데 처음에 만든값은 1~6일떄 9고 여기서는 8로 다시배열되긴했는데 이유를 알수있을까요?

#7

디버거 키고 변수 추적해보세요.

펜져님이 이상한걸 물들였어…

#8

12
12.jpg1512×2016 1.13 MB
13
13.jpg3024×4032 4.33 MB

디버거 하는방법 찾아서 해봤는데 i값에대한 출력하는 dist[i]가 왜 8이아니고 9인지 궁금한건데 돌리다보면 dist[6] 이 9인거만뜨고 어느변수값을 추적해야 출력값에 대한 정보를 구할수있을까요?

#9

i가 6인데 dist에서 6번째에 해당하는 값이 9네요.

#10

밑에 추가한 코드로 출력했을때는 8로11
이런식으로 나오는데 변수자체는 바꾼게 하나없고 index만 추가한거거든요… 답도 8이 맞다고하는데 위에코드로했을때는 dist [6] = 8 이아니라 9가뜨네요… 왜 값같은거 바꾼거 하나없는데 1~6 : 9로 뜨는지 이유를 모르겠어요ㅠㅠ

#11

디버거를 해도 1~6이 8이나오는과정 1~6이 9가 나오는과정이 어느부분인지 모르고 dist [6] = 9 이런식으로만 뜨는데 혹시 방법이있을까요

#12

dist에 어떤 값이 들어가는지 추적해보셔야 할거 같습니다.

디버거와 함께 머릿속에서도 코드를 한번 돌려보세요.

#13

음 생각을 안해본건아니지만 조금더 생각해보겠습니다ㅠㅠ!
그래도 잘 이해가안되거나 모르면 그때 다시 답글드리겠습니다. 감사합니다

#14

break point 와 watch 를 익히셨군요
축하드립니다.
코드가 실행되는 과정들을 따라가는데 익숙해지시면
이런건 타인에게 질문할 필요가 없죠.

물론 소스코드라는 자기표현을 따라가는데 익숙해지면
수억번 돌릴 필요도 없구요.
( 뇌가 피곤할땐 그래도 디버거를 써야되긴 합니다만 )

#15

이 부분 의도하신건가요?

#16

만약 의도하신 게 아니라면 해당 코드를 수정하면 다음과 같습니다.

   for (int i = 1; i <= N; i++) {
      min = INF;
      for (int j = 1; j <= N; j++) {
         if (min > dist[j] && flag[j] == 0) {
            min = dist[j] + data[j][0];
            position = j;
         }
      }

실행결과

3 Likes
#17

앗… 제가 생각한건 j였는데 i로 들어가있네요…(?) 출력값이 원하는대로 나와서 몰랐네요

#18 
#include <stdio.h>
#include <stdlib.h>

#define N 6
#define INF 9999

int flag[N + 1];
int dist[N + 1];

int i, j, min, position;

int data[N + 1][N + 1] = {
	{0, 0, 0, 0, 0, 0, 0},
{0, 0, 2,INF, 3,INF,INF},
{0,INF, 0, 4 , 1, 7,INF},
{0,INF,INF, 0, 4, 1, 3},
{0,INF, 2, 2, 0, 1,INF},
{0,INF,INF, 1,INF, 0, 6},
{0,INF, 3,INF, 8,INF, 0}
};


void main()
{
	for (i = 1; i <= N; i++) {
		flag[i] = 0;
		dist[i] = INF;
	}

	dist[1] = 0;

	for (i = 1; i <= N; i++) {
		min = INF;
		for (j = 1; j <= N; j++) {
			if (min > dist[i] && flag[j] == 0) {
				min = dist[i] + data[i][j];
				position = j;
			}
		}
		flag[position] = 1;

		for (j = 1; j <= N; j++) {
			if (dist[j] > data[position][j] + dist[position] && data[position][j] != INF) {
				dist[j] = data[position][j] + dist[position];
			}
		}
	}

	for (i = 1; i <= N; i++) {
		printf("1 ~ %d : %d \n", i, dist[i]);
	}
}

이코드에서 결과값이
1 ~ 1 : 0
1 ~ 2 : 2
1 ~ 3 : 5
1 ~ 4 : 3
1 ~ 5 : 4
1 ~ 6 : 9 가 나오는데 변수나 값같은거 크게바꾼거없었는데 위에 제가더추가한코드나 님이 수정해주신 코드로 작성한 결과값은 1~6 : 8이 나오는데… 머릿속으로생각을하든 디버그를 하든 1~6 : 8인걸로 코드를 짜서인지 왜 9가 나오는지 이유를 못찾겠는데 혹시 해설가능할까요… ㅠㅠ

#19

1~6 : 8이 맞다고하는데 변수의값같은거 변화없이 추가만했는데 1~6 : 9 였던게 왜 1~6 : 8로 바뀌면서 제대로 출력되는지 그 이유가 궁금합니다. 디버그열심히해도 애초에 8로 생각해서 짠거여서인지… 아무리 생각해도 잘모르겠네요 ㅠㅠ

#20

그냥 디버그(?) 해봐라 그럴수도있지만… 혼자 생각해보고 돌려보고 했는데 1~6 : 9로 출력되는이유는 도저히 못찾겠더라구요…