목록백준 2206 (1)

시작이 반

[백준] 2206번(python 파이썬)

미로와 같은 방식으로 풀 수 있지만 벽을 최대 한번 부실 수 있다는 조건이 있다. 처음 생각한 방법은 다음 좌표에 대해서 벽이 있을경우 그 벽을 깨고 그 자리에서 다시 BFS를 수행하는 것이었다. 즉 BFS( BFS ) 이렇게 중첩이 되는데 제출 결과 시간 초과 에러가 나왔다. 시간 복잡도를 보게되면 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색하니까 O(NM)^2)가 된다. 배열의 가로와 세로의 입력이 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000) 이렇게 제한이 되어있는데 N과 M이 1000일경우 NM은 1,000,000이 되고 NM^2은 1,000,000,000,000가 되니.. 시간초과가 뜨는게 당연하다. 3시간이나 붙잡고 풀었는데 참... 정..
알고리즘/백준 2021. 1. 8. 15:03
이전 Prev 1 Next 다음