BOJ 14502. 연구소

14502번: 연구소 (acmicpc.net)

14502번: 연구소

처음 봤을 때는 상당히 당황스러운 문제였다.

 

어느 부분에 벽을 놓아야 할지 감이 잘 안왔던 문제였는데 문제에서 한가지 힌트를 얻었다.

안전 영역의 크기를 구하는데 최댓값을 구하라는 걸 보니 여러 번 시도하는 문제라는 것을 알 수 있었다.

 

그렇다면 가장 쉬운 방법으로 BFS를 Backtracking하여 푸는 문제로 생각이 들었다.

그러면 시간복잡도는 어떻게 될까?

연구소의 크기가 최대 8*8이고 여기서 벽을 3개 세워야 하므로 64C3을 해야 한다.

나중에 한번 훑으면서 안전 영역의 크기를 구해야 하므로 또다시 8*8이 된다.

 

즉, O(n) = 64*64C3*64 = 170,655,744로 C++ 기준 2초가 넘지 않으며 python기준 최대 8초이다.

(C++은 1초에 약 1억번의 연산이 가능하고 파이썬은 1초에 약 2천만번의 연산이 가능하다)

 

적당한 연산횟수인 것 같으므로 구현해보자.

벽을 세우는 경우의 수를 조합과 순열을 이용해 구했다.

같은 코드를 pypy3로 돌리니 시간이 훨씬 줄어들었다.