공부용

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 여러 개의 섬에 섬과 섬을 이을 다리를 놓을 때, 여러 방법이 있겠지만 이 문제에서는 가장 거리가 짧은 한 개의 다리만을 선택해서 놓기로 한다. 이때 가장 짧은 다리의 길이를 구하는 문제이다. 나는 다음과 같은 방법으로 풀었다. 1. 먼저 한 섬에 대해 BFS를 하면서 그 섬과 인접한 바다의 좌표를 모두 저장 2. 이후 1에서 저장한 좌표를 가지고 아직 방문하지 않은 섬을 만날 때까지 BFS를 하고, ..