Baekjoon 17472 다리 만들기 2 JAVA

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

17472번: 다리 만들기 2

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2017472

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 map을 통해 섬이 주어지고, 섬들을 모두 이을 수 있는 다리를 만들어서

모두이었을 때 다리의 거리가 최소가 되는 값을 구하는 문제다.

조건으로 다리길이는 2 이상이어야 한다.

​

해당 문제는 BFS, TreeMap, 크루스칼 알고리즘을 사용해서 해결했다.

먼저 각 섬을 BFS를 통해 번호를 바꿔주고 이후 각 섬들의 테두리 좌표를 q에 삽입한 뒤

4방 탐색을 통해 각 섬에서 다음 섬으로 연결되는 부분에 대해서 TreeMap에 삽입해 준다.

key 값으로 시작 종료되는 섬의 번호를 value는 거리를 넣어주는데 이때 섬의 번호가

작은 게 앞으로 오도록 해주고 거리는 -1을 해준다

또 기존의 값이 있으면 가져오고 없으면 9999라는 값을 가져와서 비교를 통해 작은 값으로 갱신해 주면서

중복을 제거해 준다.

이후 map에 저장된 값을 2차원 배열로 가져와서 람다식을 통해 거리가 가까운 순으로 정렬하고

크루스칼 알고리즘을 사용해서 최솟값을 구해서 출력해 준다.