17472번 - 다리 만들기 2
1. 섬들을 묶어서 생각하지 말고 한칸한칸 다 따로 생각하세요.
2. 섬들 간 연결이 가능하다면 (가로나 세로가 같을 것, 사이에 섬이 없을 것, 길이가 1이 아닐 것) edge를 우선순위 큐에 담으세요. 당연하지만 붙어있는 두 섬 역시 길이가 0이므로 담을 수 있습니다.
3. union-find로 MST를 찾으세요.
코드도 상대적으로 짧고 이해하기도 쉬운 방법이네요 ㄷㄷ
감사합니다
wow 진짜 멋진 풀이네요
댓글을 작성하려면 로그인해야 합니다.
a41798175 3년 전 4
1. 섬들을 묶어서 생각하지 말고 한칸한칸 다 따로 생각하세요.
2. 섬들 간 연결이 가능하다면 (가로나 세로가 같을 것, 사이에 섬이 없을 것, 길이가 1이 아닐 것) edge를 우선순위 큐에 담으세요. 당연하지만 붙어있는 두 섬 역시 길이가 0이므로 담을 수 있습니다.
3. union-find로 MST를 찾으세요.