트리에서 최단 경로를 구하기 위한 또 다른 방법?
간선의 가중치가 모두 같고, 최단 거리를 구하라 그러면 BFS를 써야 한다. 고 생각하시는 경우가 많습니다. 네. 대부분의 경우에는 맞습니다. 그런데 몇 문제는, 특수한 조건을 줍니다. 이 때에는, BFS를 쓰는 게 답이 아닐 수도 있습니다. 백준 10838번 문제를 봅시다. 일단 솔브드 티어로 골드3. 상당히 만만해 보입니다. 보통 이 경우에는 BFS, DFS 응용 문제들도 많이 분포해 있기 때문에, 최단거리가 나왔다. 그러면 다익스트라나, BFS로 섣불리 판단하기 쉽습니다. 문제는 굉장히 길기 때문에, 따로 설명을 드리지는 않겠습니다. 잘 읽어보셨다면 중요한 조건이 몇 가지 있다는 것을 알 수 있는데요. 트리의 노드 갯수는 10^5개 이하입니다. 여기서 왜 제가 4개의 조건에 밑줄을 쳤을까요? 4개 ..
자료알고/알고리즘
2020. 2. 2. 15:07
최근댓글