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 제한이 작을 때만 사용해야한다. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 ··· 29 30 31 32 다음