백준 2234. 성곽

https://gist.github.com/LSH3333/8ddd37de404019d14cd5beec744827b2

2234.cpp

 

1번 2번은 bfs 돌려서 구하면 된다.

3번은 벽 하나를 부시고 -> bfs 돌리고 -> 복구하고 를 반복하면 되는데 성의 가장 바깥 부분은 사실 부숴볼 필요가 없지만 그냥 부숴도 시간초과는 안날거같아서 부숴봤는데 시간초과가 난다.

가장 바깥 부분은 부수지 않았더니 통과.

 

 

 

 

---

다른 분들이 푼 방법을 보니 3번 조건을 구하는데 시간을 훨씬 줄이는 방법이 있었다.

dfs든 bfs든 하나의 방에 방 번호를 부여하며 각 방의 크기를 저장해 놓는다.

벽 하나를 허문다는 것은 인접한 두 다른 번호의 방이 합쳐지는 것이기 때문에 구해 놓은 두 방의 합이 된다.