연결된 무방향 가중 그래프(G)의 모든 간선의 가중치에 동일한 양수 c… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
연결된 무방향 가중 그래프(G)의 모든 간선의 가중치에 동일한 양수 c를 더하여 새로운 그래프(G′)를 만들었다. G와 G′를 비교하였을 때, 최소 신장 트리(minimum spanning tree)의 변화 여부와 모든 두 정점 간 최단 경로의 변화 여부에 대한 설명으로 가장 옳은 것은?
1
최소 신장 트리와 최단 경로가 모두 그대로 유지된다.
2
최소 신장 트리는 그대로 유지되지만, 최단 경로는 달라질 수 있다.
3
최소 신장 트리는 달라질 수 있지만, 최단 경로는 그대로 유지된다.
4
최소 신장 트리와 최단 경로가 모두 달라질 수 있다.
해설

최소 신장 트리는 그대로 유지되지만 최단 경로는 달라질 수 있다.

신장 트리는 항상 간선이 V−1개이므로 모든 신장 트리의 가중치가 똑같이 (V−1)c만큼 늘어 순위가 바뀌지 않는다.

반면 경로는 간선 수가 제각각이라 간선 k개짜리 경로는 kc만큼 늘어난다. 예컨대 A–B 직접 간선이 3이고 A–C, C–B가 각 1이면 원래는 우회 경로(2)가 최단이지만, c=2를 더하면 직접 간선은 5, 우회 경로는 6이 되어 최단 경로가 직접 간선으로 바뀐다.

  • 둘 다 유지된다: 간선 수가 많은 경로가 더 크게 불리해지므로 최단 경로는 유지되지 않을 수 있다.
  • 최소 신장 트리만 달라진다: 모든 신장 트리가 같은 양만큼 늘어나므로 최소 신장 트리는 바뀌지 않는다.
  • 둘 다 달라질 수 있다: 최단 경로는 맞지만 최소 신장 트리는 바뀌지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기