js0304   1년 전

안녕하세요, 매번 도움 많이 받아갑니다.

이번 문제를 풀이하며, 두 가지 방법으로 코드를 구성했습니다.

첫 번째는 벽마다 bfs를 진행해주는 방식으로, 시간초과가 났습니다.

두 번째는 빈 공간에 대해 bfs를 진행하여 이어진 빈 공간에 인덱스를 부여하고, 이후 벽에 대해 상하좌우 인접한 인덱스의 0 개수를 더해주는 방식으로 정답을 받았습니다.

제가 드는 의문은, 물론 빈 공간들이 많은 경우 두 번째 방식이 더 빠르겠지만,

010101010...

101010101...

010101010...

101010101...

.

.

.

처럼 결국 벽에 대해 bfs를 진행하든 빈 공간에 대해 진행하든 결국 같은 시간이 걸리는 게 아닌가 하는 의문이 듭니다. 시간 복잡도에 대한 제 이해가 짧은 것인지, 조언 부탁드리겠습니다.

zenith82114   1년 전

거대한 빈 공간에 많은 벽이 접해있을 경우, 벽마다 BFS를 하면 벽 1칸마다 빈 공간 면적에 비례하는 시간을 쓰면서 면적을 새로 계산합니다. 반대로 빈 공간들에 대해서 BFS를 해놓으면 1번만 계산한 면적을 인접해 있는 벽들에게 더해 주기만 하면 됩니다.

js0304   1년 전

그 이후 과정에서의 차이였군요.

감사합니다!

댓글을 작성하려면 로그인해야 합니다.