BOJ 1261

알고스팟이라는 문제인데... 음 처음에는 그냥 bfs로 다 탐색하면서 벽을 뚫을 때마다 벽을 뚫은 개수를 d[i][j]에 기록하면서 나가면서, 더 적게 뚫은 경우가 있으면 update해주고 큐에 넣는 식으로 풀었는데, 4ms라는 시간이 나왔다.

다른 분들을 보니 0ms에 푼 분들도 많았다. 그래서 백준님의 풀이 설명을 보니 큐를 2개 이용하거나 덱을 써서 벽이 없는 부분으로만 갈 수 있는 경로와와 벽을 하나 뚫고 갈 수 있는 경로로 나눠서 단계별로 bfs를 실행 시켰고, 그렇게 단계별로 실행함으로 인해, 내가 원래 풀었던 방식에서 있었던 중복된 방문과 update가 없어도 되는 것 같다. 한번 씩만 방문하게 되어 더 시간이 절약되고...

덱을 사용해서 내가 다시 풀어봤는데.. 정말 덱을 이렇게 쓸 수 있다니... 감탄이 나왔다. 덱이 처음에는 별 사용도 안될 필요없는 자료구조인 줄 알았는데 오늘 알고스팟 문제를 풀면서 덱의 멋짐, 아름다움을 느꼈다...
그리고 이 덱을 사용한다는 풀이를 하는 분들도 정말 대단하신 것 같다.

여튼 그래서 0ms에 풀었다. 근데 아직 이해가 안되는 것은 복잡도가 O(n^2)이 나온다는 것인데, 이것이 무엇을 뜻하는지 잘 모르겠다. 한번 메일로 질문해볼까 생각중이다.
-> 백준님게 답장이 왔는데, O(nm)을 뜻하는 거라고 하신다. 내 추측이 맞은 것 같다.