16918 봄버맨

16918 봄버맨 / c++ / Silver1 / 1시간+

문제 및 코드

풀이 과정

구현

1. 주어진 설명대로 구현하면 되는 문제이다. 그런데 그냥 구현하려고 하면 문제가 좀 있었다.
2. 처음에 직접 시간을 증가시키며 격자판을 시뮬레이션 해봤는데, N = 0, 1, 2, 3 를 반복한다는 것을 깨달았다. (N%4)
   1. 입력 N은 0부터 주어지므로 N%4==0이라면 N은 4,8,12,…
   2. 시작 후 1초는 아무것도 하지 않는다. (격자판 그대로 출력)
   3. 2초에는 빈 칸에 폭탄을 설치하기 때문에 폭탄으로 가득찬 격자판을 출력
   4. 3초에는 0초에 설치한 폭탄들이 터진다. (0초 초기 상태를 A라고 했을 때, 이 0초에 설치한 폭탄이 터진 상태를 B라고 가정해보자)
   5. 4초에는 다시 빈 칸에 폭탄을 설치하므로 가득 찬 격자판을 출력 (N==2 때와 동일)
   6. 5초(N==1)에는 다시 시작 후 1초와 동일한 상태가 된다.
   7. 6초(N==2)에는 시작 후 2초와 동일한 상태가 된다.
   8. …
3. 이렇게 풀었는데 틀렸다.
4. 질문글에 있는 답변을 확인했는데
   • 3 3 5
     O O .
     O O O
     O O O
   • 위의 경우에는 N=5,(N%4==1) 이므로 입력값과 같은 결과가 나올 것 같지만,
   • O O O
     O O O
     O O O
   • 이런 답이 나온다.
     (2초에 설치한 폭탄이 3초에 터져버려서 4초에 이미 다른 폭탄으로 메꿔진 경우)
5. 그래서 생각한 것이, 터질 폭탄의 위치를 기억해 둔 후, N초에 해당 폭탄이 터질지를, N-3초에 터진 폭탄의 주변인지 여부로 확인할 수 있지 않을까? 였다.
6. 그래서 Boom 이라는 함수에서 폭탄을 터트릴 때, CheckIsRemain(남아있는지 여부)함수로 3초 전에 터지지 않았는지를 체크했다.
7. 해결 (하지만 시간복잡도가 600ms가 나와버림)
8. 0ms 에 해결한 다른 분의 코드를 보니, 폭탄을 .과 O로 구분하는게 아닌, 3,2,1,0 으로 그 자리에 남은 시간을 저장해서 사용하셨다.
9. 이걸 보고 머리가 띵했다. 왜 정보를 저렇게 저장할 생각을 못했을까..?
10. 제출했던 코드를 격자판에 폭탄의 남은 시간 (0이라면 빈칸)을 기록하게 수정했다. 그러고나니 CheckIsRemain 과 같은 함수를 사용할 필요도 없었다.
11. 시간 복잡도 0ms 로 해결!

    다시 생각해 볼 점

12. 문제에서 주어진 정보대로 사용하지 말고 내가 필요한 형식으로 재가공해서 사용해야한다는 점을 크게 깨달았다.
13. 예전에는 항상 분석, 정보 재가공, 풀이 순으로 진행했었는데, 이 방식이 다시 습관이 될 수 있게 노력해야겠다.