트리
-
최소신장트리: 백준 9372 상근이의 여행PS 2022. 7. 23. 14:38
최소신장트리: 백준 9372 상근이의 여행 간단한 팁을 하나 남겨보고자 포스팅을 합니다. 제목에 쓰여있듯이 신장트리(spanning tree)라는 것에 대한 이야기예요. 문제와 풀이 문제 링크 : 백준 9372 - 상근이의 여행 👇펼쳐서 코드와 해설 읽기 문제를 보면 즉시 BFS로 풀어야겠다는 생각이 들죠. 최소신장트리에 대해서 모르는 상태였기 때문에 저도 그랬습니다. 신장 트리란 모든 정점을 포함하고 있는 그래프를 말합니다. 그리고 모든 정점을 가장 짧은 경로로 연결하는 그래프를 최소 신장 트리라고 합니다. 물론 몇가지 제약이 있지만 일단 개념은 그렇습니다(무향 그래프에서 가중치나 비용이 특별히 없을 때). 최소신장트리가 그려질 때에는 한 그래프에서 여러 형태로 존재할 수 있고, Self loop는 불..