다익스트라입니다 ㅠ

#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 이대로 수정을 하고
(설정한 변수같은거 안바꾸고 가르쳐주셔야되요 ㅠ 말그대로 전과해서 뉴비에요…)
그리고


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

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

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

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

열심히 공부하겠습니다 ㅠ

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

#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로 다시배열되긴했는데 이유를 알수있을까요?

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

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


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

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

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

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

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

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

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

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

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

이 부분 의도하신건가요?

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

   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

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

#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가 나오는지 이유를 못찾겠는데 혹시 해설가능할까요… ㅠㅠ

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

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