pulchra13   2년 전

분류가 MST로 되어있네요

저는 다익스트라에서 배열하나만 추가해서 풀었고

다른분들 풀이 보니까 대부분 다 그렇던데...

이걸 MST알고리즘으로 풀 수가 있나요

aeternussm   2년 전

1. 모든 칸마다 인접한 칸과 이어주는 거리를 높이 차이 절댓값으로 하는 간선을 만듬

2. 거리가 작은 순으로 집합을 합쳐줌 (크루스칼)

3.  union 할 때마다 출발지와 도착지의 집합이 같은지 확인

4. 집합이 같아지는 순간 합친 간선의 거리가 정답

amsminn   2년 전

작은간선부터 이어주면서 확인해보는데 그 형태가 크루스칼과 비슷해서 그런 것 같네요

댓글을 작성하려면 로그인해야 합니다.