[BOJ] 14502. 연구소 (JavaScript)

 

문제 url: www.acmicpc.net/problem/14502

14502번: 연구소

회고

• 처음 (대충) 봤을때 바이러스 확산으로 공간을 채우는 과정이 있기 때문에 BFS로 풀면 될 것 같았다
• 그런데 벽 3개를 무조건 세워야 한다는 조건을 보고 DP로 풀어야 하는 건가 싶었다
• DP로 풀기에는 점화식을 찾아내기가 너무 어려울 것 같았다
• 그냥 일단 벽 3개를 brute force로 해보고 최적화를 해보자는 생각으로 구현했는데 그냥 이렇게 하는게 맞았다..

풀이 과정

• 벽 3개를 세워야 하기 때문에 전체 영역을 돌면서 벽을 세우는 과정이 필요
  • 무려 6중 for-loop.. 
• virus: 벽 3개가 세워지면 BFS/DFS로 바이러스 확산시킴
  • 시간이 지날 때마다 원래 바이러스 위치로부터 감염 영역 지름이 1씩 증가하므로 함수명은 BFS로 지었지만
  • 함수 호출은 DFS 방식으로 발생함
• getSafeNum: 전체 영역을 다시 한번 돌면서 안전 영역("0")의 개수를 구함

---

풀이 코드