BOJ 2146 - 다리 만들기

문제 링크

---

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

문제 해결

---

1. BFS를 이용해서 각 대륙(0이 아닌 곳)에서 바다(0인 곳)와 인접해있는 곳에 새로운 번호를 부여.

  

2. 각 번호에서 0,1,자기 자신의 번호 이외의 값을 만날 때까지 다시 BFS.

주의할 점

---

BFS를 이용해서 새로운 번호를 부여하는 시간 복잡도는 O(N^2)이지만, 새로 번호를 부여받은 곳에서 다른 대륙까지의 BFS를 이용할 시 O(N^4)까지 올라갈 수 있으므로, N 제한이 작을 때만 사용해야한다. 

※ 정확하고 부드러운 태클은 언제나 환영입니다.