플로이드 워셜 관련 질문
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
플로이드 문제에서 가령 입력값이 아래와 같다고 할 때, 5 4 1 3 10 3 2 1 1 5 1 5 3 1 d[1][2] 의 값은 K = 3 일 때 d[1][2] = d[1][3] + d[3][2] = 11 그런데 d[1][3]은 이후에 K가 5일 때 연산을 통해 d[1][3] = d[1][5] + d[5][3] = 2 근데 작아진 d[1][3]의 값이 반영되려면 K가 5일 때, d[1][5] + d[5][3] 연산을 한 '이후에' K가 3일 때 d[1][2] =d[1][3] + d[3][2] 연산을 통해 d[1][2] 의 값이 바뀌어야 한다고 생각이 드는데 점점 증가해야 하는 K값이 값자기 작아질수는 없으니 그건 불가능합니다. d[1][2]의 값이 3이 되는데 필요한 어떤 연산을 제가 놓친건지 모르겠습니다...
- c++
- 플로이드
토모시키
댓글 2
좋아요 0
조회수 184