나의 논리
문제의 조건에서 바이러스가 퍼지는 조건을 보고 BFS로 풀어야겠다고 생각했는데 벽을 세우는 것 때문에 처음에 이것이 BFS문제가 맞는지 고민을 했다. 벽을 노드로 보고 BFS로 풀어야하는지.. 바이러스를 노드로 보고 BFS로 풀어야 하는지..
그러나 어느정도 고민 후 다음과 같은 결론에 이르게 되었다.
벽을 세운다는 것은 N x M 크기의 직사각형에 3개를 세우기 위해 모든 경우의 수를 따져보아야 한다.
벽을 어떻게 세워야 한다는 공식은 문제에 없었고, 떠오르는 공식도 없었기때문에
단순하게 모든 경우의 수를 따져보는 브루트 포스로 벽을 세우기로 결정했다. 그리고 세워야 하는 벽의 갯수가 3개 밖에 안되기 때문에, 이것은 호출스택의 깊이가 그렇게 깊지 않다는 뜻이다. 해볼만하다고 느꼈고
벽을 3개 세웠을때, 바이러스가 퍼지는 것을 BFS로 시물레이션 한 후, 바이러스가 더이상 퍼질 수 없다면 BFS코드를 종료하고 안전한 공간의 총 갯수를 세어 그 수를 리턴한다.
3개의 벽을 세우는 모든 경우의 수에 대하여 이 BFS연산을 반복하여 최댓값을 찾는다.
NxM 직사각형이므로 호출스택 1번에 대하여 나올 수 있는 경우의 수는 NM가지이다. 그리고 총 깊이가 3이므로 NM가지의 경우의 수가 3번 나온다. 경우의 수는 (NM)^3 가지이고 각 경우의 수마다 BFS를 수행하는데 이 로직에서 시간복잡도는 NM이다. 그래서 총 시간복잡도는 (NM)^4이고 약 1천6백만개의 경우의 수가 나온다.
시간안에 해결 할 수 있을 것 같았다.
코드를 실컷 짜놓고 값이 안나와서 로직에 문제가 있는가 싶어 한참을 찾았었다.
그러다가 눈에 보인것이 벽의 갯수를 세는 cnt에 문제 있었다.
처음에는 다음 스택에 cnt를 cnt++로 넘겨줬었는데 이렇게 되면 현재스택의 cnt 까지 바뀌어서 다른 경우의 수를 탐색해야될때 cnt가 아니라 cnt+1인 상태로 현재스택에서 다음경우의 수를 탐색하게 된다.
다음 호출 스택에 값에 의한 매개변수를 넘겨줄때 cnt+1을 하자…
