백준 17472 (다리만들기2) / KruskalMST

dudrkdl777·2019년 10월 10일
0

https://www.acmicpc.net/problem/17472

백준 17472 - 다리만들기 2

사용한 자료구조 및 알고리즘

  • MST (최소신장트리)
    - Prim 과 Kruskal중 비교적 쉬운 Kruskal로 구현하였음.
  • BFS (넓이우선탐색)

논리 구조

  1. '모든섬을 다리로 연결해야한다'는 포인트에서 mst를 사용해야겠다고 생각.
  2. mst를 위한 시작노드 , 종료노드 , 가중치를 2차원 배열에서 어떻게 가져와야할까?
  3. 섬에 번호를 붙이는 라벨링 과정을 통해 일단 섬을 구별시킴 (BFS로 구현)
  4. 탐색을 시작하는 섬에서 상,하,좌,우로 다른섬을 만날때까지 이동시켜본다.
  5. 시작섬의 번호를 시작노드, 도착하는 섬의 번호를 종료노드 , 이동거리를 가중치로 두고
  6. 우선순위 큐에 모든 경우의 이동가능 경로를 저장하고
  7. 최소 신장 거리는 Kruskal Mst 알고리즘에 맡겼다!

느낀점

하 이문제는 8월 삼성 역량테스트에서 만난 문젠데 당시에는 손도 못댔었다. 심지어 당시에는 MST를 써야겠다는 생각조차 못했는데 이제서야 풀었다...심지어 mst는 참고했음 ㅜㅜ
소요시간은 약 2시간 쉽지않다 쉽지않아~...
역량테스트 과락 이후 손 놓았던 prim, kruskal mst와 다익스트라 복습이 절실히 필요한것같다!
다음에는 외워서 풀어야지 흑..

code

profile
1일1커밋

0개의 댓글