11780 플로이드 2

 

https://www.acmicpc.net/problem/11780

11780번: 플로이드 2

 

플로이드워셜로 최단거리 구하고 경로 역추적하는 문제

 

플로이드 워셜은 검색하면 많이 나오니 설명 X

 

다익스트라 역추적하고 비슷한데, 

거리 최소값 갱신될 때, 경로추적용 parent 배열값이 바뀌는건 맞으나

제일 중요한 디테일 하나가 있다면

if ( A[i][k] + A[k][j] < A[i][j] )
{
    A[i][j] = A[i][k] + A[k][j];
    parent[i][j] = parent[k][j];
}

여기서 

parent[i][j] = parent[k][j];

이 코드가 핵심이다

뭔가 자명한듯 하나, 그래도 엄밀한 설명이 필요하다

다른 블로그를 좀 뒤져봤으나 저거에 대해서 제대로 설명하는 블로그가 단 1도 없다 ㅋㅋㅋㅋ

자명한건지 아니면 걍 코드 갖다 배껴서 푸는건지... 근데 나도 좆밥이라 뭐 욕할 처지는 아니다.

증명할 능력이 안되니 걍 넘어가자

Proved by AC !

 

뭐 이후는 다익 역추적이랑 비슷하게 걍 코드짜면 된다. 다익은 한 정점에 대해서 최단거리 계산이라 parent 배열이 1차원이지만, 플로이드 워셜은 모든 정점에 대해서 다루므로 2차원 parent 배열을 이용해서 시작 지점이 i, 도착 지점이 j 일때 경로 추적을 계속 해주면 된다. 경로추적법은 하도 이전 글에서 다뤘으므로 여긴 걍 패스

 

https://github.com/KimximyaFan/Random-Defense/blob/main/C0037.java