1. 모든 칸마다 인접한 칸과 이어주는 거리를 높이 차이 절댓값으로 하는 간선을 만듬
2. 거리가 작은 순으로 집합을 합쳐줌 (크루스칼)
3. union 할 때마다 출발지와 도착지의 집합이 같은지 확인
4. 집합이 같아지는 순간 합친 간선의 거리가 정답
22116번 - 창영이와 퇴근
1. 모든 칸마다 인접한 칸과 이어주는 거리를 높이 차이 절댓값으로 하는 간선을 만듬
2. 거리가 작은 순으로 집합을 합쳐줌 (크루스칼)
3. union 할 때마다 출발지와 도착지의 집합이 같은지 확인
4. 집합이 같아지는 순간 합친 간선의 거리가 정답
댓글을 작성하려면 로그인해야 합니다.
pulchra13 2년 전
분류가 MST로 되어있네요
저는 다익스트라에서 배열하나만 추가해서 풀었고
다른분들 풀이 보니까 대부분 다 그렇던데...
이걸 MST알고리즘으로 풀 수가 있나요