16946번 - 벽 부수고 이동하기 4
안녕하세요, 매번 도움 많이 받아갑니다.
이번 문제를 풀이하며, 두 가지 방법으로 코드를 구성했습니다.
첫 번째는 벽마다 bfs를 진행해주는 방식으로, 시간초과가 났습니다.
두 번째는 빈 공간에 대해 bfs를 진행하여 이어진 빈 공간에 인덱스를 부여하고, 이후 벽에 대해 상하좌우 인접한 인덱스의 0 개수를 더해주는 방식으로 정답을 받았습니다.
제가 드는 의문은, 물론 빈 공간들이 많은 경우 두 번째 방식이 더 빠르겠지만,
010101010...
101010101...
.
처럼 결국 벽에 대해 bfs를 진행하든 빈 공간에 대해 진행하든 결국 같은 시간이 걸리는 게 아닌가 하는 의문이 듭니다. 시간 복잡도에 대한 제 이해가 짧은 것인지, 조언 부탁드리겠습니다.
그 이후 과정에서의 차이였군요.
감사합니다!
댓글을 작성하려면 로그인해야 합니다.
js0304 1년 전
안녕하세요, 매번 도움 많이 받아갑니다.
이번 문제를 풀이하며, 두 가지 방법으로 코드를 구성했습니다.
첫 번째는 벽마다 bfs를 진행해주는 방식으로, 시간초과가 났습니다.
두 번째는 빈 공간에 대해 bfs를 진행하여 이어진 빈 공간에 인덱스를 부여하고, 이후 벽에 대해 상하좌우 인접한 인덱스의 0 개수를 더해주는 방식으로 정답을 받았습니다.
제가 드는 의문은, 물론 빈 공간들이 많은 경우 두 번째 방식이 더 빠르겠지만,
010101010...
101010101...
010101010...
101010101...
.
.
.
처럼 결국 벽에 대해 bfs를 진행하든 빈 공간에 대해 진행하든 결국 같은 시간이 걸리는 게 아닌가 하는 의문이 듭니다. 시간 복잡도에 대한 제 이해가 짧은 것인지, 조언 부탁드리겠습니다.