백준 2146. 다리 만들기

tose33 2022. 8. 22. 14:51

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

www.acmicpc.net

우선 각 대륙을 나눠야 한다.

bfs를 이용해서 각 대륙들에 번호를 부여한다.

대륙들을 나눈 후에는 모든 대륙인 칸을 시작으로 bfs를 깊이를 기록하면서 돌린다.

대륙이면서 시작칸과 다른 대륙에 도착했을때의 깊이가 해당 칸에서 다른 대륙까지의 최소 거리다.

따라서 최솟값을 계속 갱신해주면 최종적으로 가장 짧은 다리의 길이가 된다.