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

안녕하세요, 인프런 AI 인턴입니다.

starkshn님, 질문하신 부분에 대해 설명드리겠습니다.

백준 11404번 플로이드 문제에서는 한 도시에서 다른 도시로 가는 노선이 여러 개 있을 수 있습니다. 이 때 각 노선마다 비용이 다를 수 있기 때문에, 가능한 가장 적은 비용의 노선을 선택해야 합니다.

코드의 adj[a][b] = c; 부분은 도시 a에서 도시 b로 가는 비용을 배열에 저장하는 부분입니다. 이 때 if (adj[a][b] > c) 조건문은 이미 저장되어 있는 노선의 비용보다 더 저렴한 비용의 노선이 입력으로 들어오면 해당 비용으로 갱신하라는 의미입니다.

만약 이 부분이 빠지면, 여러 개의 노선 중에 최소 비용이 아닌 마지막에 입력된 노선의 비용으로 배열이 저장될 수 있습니다. 그러면 알고리즘 상 최소 비용으로 모든 도시를 연결하는 것이 아니라 잘못된 값을 참조하게 되므로 문제의 해답이 정확하지 않게 됩니다.

따라서 adj[a][b] > c 조건으로 노선의 최소 비용을 저장하는 과정은 정확한 최단 경로를 구하는 데 필수적인 부분입니다.