[BOJ]2146번: 다리 만들기(py)

www.acmicpc.net/problem/2146

---

BFS 문제입니다.

N제한이 100이므로 BFS로 전체 그래프를 한 번 탐색하는데 O(100*100)이 걸립니다.

그러므로 BFS를 딱 한 번만 돌아서 모든 섬간의 최소 거리를 구해줘야합니다. (시간초과 X)

 

1. 섬을 컴포넌트 별로 나눕니다.

2. 컴포넌트 별로 나눈 모든 섬들의 좌표를 큐에 넣습니다.

3. 섬 = '방문한 칸', 바다 = '방문하지 않은 칸'이라는 의미로 BFS를 돕니다.

4. 서로 다른 컴포넌트인 두 섬이 BFS로 영역을 확장하다 만나면 그 둘이 지나온 거리를 더하면 정답입니다.

 

무슨 말인지 이해가 잘 안가신다면 아래 코드를 참고하시면 됩니다.

---

코드: github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ2146.py