[BOJ] 백준 17472 다리 만들기 2 (JAVA)

BFS + MST

📑 문제

백준 17472 다리 만들기 2

 

---

🌱 아이디어

BFS로 각 섬에 번호를 부여하고, 모든 섬을 연결하는 다리잇기(MST)로 구현하자

 

2차원 평면 상 섬과 바다가 입력으로 주어지고, 다리를 연결해서 모든 섬을 연결하려고 한다.

다리는 가장 짧게 연결해야 한다. 즉 모든 섬을 최소비용으로 모두 잇는다면 = 최소스패닝임을 유추해야 풀 수 있다.

 

아래와 같은 3단계를 거쳐서 구현했다.

 

1. 모든 섬을 탐색하고 번호를 부여한다 그래야 A -> B를 특정할 수 있다.

2. A -> B가 직선으로 장애물 없이 다리를 이을 수 있는지 판단 후 우선순위큐에 시작노드, 목표노드, 비용을 입력하기

3. 크루스칼알고리즘으로 모든 섬을 잇기

 

맵의 크기, 섬의 개수가 매우 작다, 시간초과를 걱정하는 것보다 차근차근 구현에 집중하는 게 좋은 문제인 것 같다!

---

🌱 코드 및 풀이

---

🌱 느낀 점

4년전 최고기록 방 빼버렸습니다 헉;;

 

MST + BFS 구현문제라서 차근차근 풀었더니 1트 만에 자바 8 기준 1등 먹었네요 맛있습니다 ㅎㅎ

성능도 같이 생각하면서 알고리즘 코딩하는 게 습관이 된듯한 느낌이네요^^