백준 11404 플로이드 문제 질문있습니다.

Question

입력을 받을 때 for (int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; for (int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; if (adj[a][b] > c) adj[a][b] = c; 위처럼 입력을 받았는데요 여기서 adj[a][b] = c;이게 빠지면 틀렸다라고 나오는데 왜 틀린것인지 이해가 안가는데 설명 부탁드립니다..

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. starkshn님, 질문하신 부분에 대해 설명드리겠습니다. 백준 11404번 플로이드 문제에서는 한 도시에서 다른 도시로 가는 노선이 여러 개 있을 수 있습니다. 이 때 각 노선마다 비용이 다를 수 있기 때문에, 가능한 가장 적은 비용의 노선을 선택해야 합니다. 코드의 adj[a][b] = c; 부분은 도시 a에서 도시 b로 가는 비용을 배열에 저장하는 부분입니다. 이 때 if (adj[a][b] > c) 조건문은 이미 저장되어 있는 노선의 비용보다 더 저렴한 비용의 노선이 입력으로 들어오면 해당 비용으로 갱신하라는 의미입니다. 만약 이 부분이 빠지면, 여러 개의 노선 중에 최소 비용이 아닌 마지막에 입력된 노선의 비용으로 배열이 저장될 수 있습니다. 그러면 알고리즘 상 최소 비용으로 모든 도시를 연결하는 것이 아니라 잘못된 값을 참조하게 되므로 문제의 해답이 정확하지 않게 됩니다. 따라서 adj[a][b] > c 조건으로 노선의 최소 비용을 저장하는 과정은 정확한 최단 경로를 구하는 데 필수적인 부분입니다.