인프런 커뮤니티 질문&답변

mhyim님의 프로필 이미지

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

8-Q

플루이드워셜 k i j 순서가 궁금합니다.

해결된 질문

작성

·

32

·

수정됨

0

큰돌님 안녕하세요?

 

플루이드 워셜 푸는데 k i j 순서가 의미가 있나 궁금해서 질문 드리게 되었습니다.

 

저의 생각은 "모든쌍에 대해 계산하므로 k i j 의 순서는 별로 상관 없다" 입니다.

그래서 코드를 이렇게 했더니 틀리더라구요?

	for(int k = 1;k<=n; k++)
	{
		for(int i = 1 ; i<=n;i++)
		{			
			for(int j = 1 ; j<=n;j++)
			{
			if(dist[k][i]==1 && dist[i][j] ==1) dist[k][j]=1;
			else if(dist[k][i]== -1 && dist[i][j] == -1) dist[k][j]=-1;
			}
		}		
	}

 

왜 큰돌님 해설 처럼 해야 하는지, 그리고 이 해설의 i k j? 순서로 해야하는지, 왜 그런지 차이가 궁금합니다.

for(int k=1; k<=n; k++)
	for(int i=1; i<= n; i++)
		for(int j=1; j<= n; j++){
                if(dist[i][k] == 1 && dist[k][j] == 1) dist[i][j] = 1;
                else if(dist[i][k] == -1 && dist[k][j] == -1) dist[i][j] = -1;
			}

답변 2

1

큰돌님의 프로필 이미지
큰돌
지식공유자

ㅎㅎ 이해하셨군요

감사합니다.

1

mhyim님의 프로필 이미지
mhyim
질문자

k i j의 순서가 상관 없는게 아니라 i 와 j를 갱신하기 위한 중간 값이 k였습니다.

제대로 안 읽은건 나였고

image.png

 

mhyim님의 프로필 이미지

작성한 질문수

질문하기