처음에 이 문제를 이분탐색 + DFS , 그리고 이분탐색 + 단순 BFS 로도 접근해 보았지만 모두 시간초과가 발생했습니다.

하지만 다른 분들의 풀이를 본 후, 아래와 같이 이분탐색 + 탐색 범위를 미리 정한 후, BFS를 사용하니 통과했습니다. 여기서 궁금한 점이 생겼습니다.

1. DFS, BFS 모두 시간복잡도가 O(V^2)이라 알고 있습니다. 문제에서는 최대 100 * 100 = 10,000개의 정점을 가지고 있기에 BFS로만하면 O(10,000^2)이 걸리고 이분탐색은 최대 O(log(2) 100) = 6.67... 정도 걸리니 이분탐색 + 단순 BFS 로 최대 6억 이상의 개수를 확인해야 하기에 시간초과가 발생하는 것이 맞는지 궁금합니다.

- 참고로 위해서 말한 단순 BFS는 큐의 인자로 ( nextY, nextX, min, max )를 주어서 다음에 갈 수 있는 방향을 정했습니다. 질문에 있던 반례는 모두 통과했지만 자료가 많아지니 시간초과가 발생했습니다...

2. 아래 코드처럼 미리 BFS로 탐색 가능한 범위(즉, i ~ i + mid 범위)를 미리 설정하고 이분탐색 + BFS탐색을 하면 왜 시간초과가 발생하지 않는 것인지 궁금합니다.

(알고리즘 공부 중이라 틀린 부분이 있으면 지적 및 정정해주시면 감사하겠습니다.)