백준 11404 플로이드 문제 질문있습니다.
262
134 asked
입력을 받을 때
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;이게 빠지면 틀렸다라고 나오는데 왜 틀린것인지 이해가 안가는데 설명 부탁드립니다..
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다.
starkshn님, 질문하신 부분에 대해 설명드리겠습니다.
백준 11404번 플로이드 문제에서는 한 도시에서 다른 도시로 가는 노선이 여러 개 있을 수 있습니다. 이 때 각 노선마다 비용이 다를 수 있기 때문에, 가능한 가장 적은 비용의 노선을 선택해야 합니다.
코드의 adj[a][b] = c; 부분은 도시 a에서 도시 b로 가는 비용을 배열에 저장하는 부분입니다. 이 때 if (adj[a][b] > c) 조건문은 이미 저장되어 있는 노선의 비용보다 더 저렴한 비용의 노선이 입력으로 들어오면 해당 비용으로 갱신하라는 의미입니다.
만약 이 부분이 빠지면, 여러 개의 노선 중에 최소 비용이 아닌 마지막에 입력된 노선의 비용으로 배열이 저장될 수 있습니다. 그러면 알고리즘 상 최소 비용으로 모든 도시를 연결하는 것이 아니라 잘못된 값을 참조하게 되므로 문제의 해답이 정확하지 않게 됩니다.
따라서 adj[a][b] > c 조건으로 노선의 최소 비용을 저장하는 과정은 정확한 최단 경로를 구하는 데 필수적인 부분입니다.
코딩 살구 클럽 Python 지원 가능 여부
0
6
0
살구클럽 아이디 없음 문제
0
13
0
1-O 코딩살구클럽 채점관련 질문
0
28
2
히든 테스트 케이스가 사라졌습니다
0
20
1
38번 문제 보기 3,4번
1
19
3
14번 문제
1
25
2
42. [세그먼트 트리 실전 문제] 구간 합 구하기3 (백준 2042)
0
69
1
10986번 질문 있습니다!
0
49
0
LCA 빠르게 찾기 - 트리의 높이에 따른 k값 질문
0
127
0
백준 1377 질문있습니다
0
221
1
백준 1722 교재 81 질문
0
337
1
백준11505, 교재 73번
0
285
1
백주 1456번
0
205
1
백준 1325, 교재 47번 문제 질문입니다.
0
363
1
문제 85번 질문드립니다
0
325
1
백준 13023 질문있습니다.
0
210
1
문제 8번 질문드립니
0
310
1
백준 1876여행 유니온 파인드 질문있습니다.
0
245
1
백준 2251 C++ 질문 있습니다.
0
403
2
퀵정렬 질문
3
295
1
i==k일떄 i++안해도되지않나요
0
439
1
알고리즘 코딩테스트 문제풀이 강의 - 14 절댓값 힙 구현하기 (백준 11286)
0
557
1
알고리즘 코딩테스트 문제풀이 강의 - 9 DNA 비밀번호 (백준 12891)
1
578
1
C++은 실전문제에 대한 강의가 없나요? 자바나 파이썬은 있는데 없는거 같아서요.
2
599
2