연구소

---

title: “14502 - 연구소”
date: “2019-02-15”

category: “algorithm”

문제요약

1. 연구소의 크기와 현재 연구소의 상태가 입력으로 들어온다. (0은 빈 공간, 1은 벽, 2는 바이러스에 감염된 공간)
2. 바이러스는 1초가 지날때마다 인접한(상하좌우) 빈 공간으로 펴져가고, 벽을 통과하지는 못한다.
3. 벽을 무조건 3개 세운뒤 얻을 수 있는 가장 넓은 바이러스에 감염되지 않은 공간을 구하여라.

접근법

이 문제 역시 BFS를 여러번 사용해야하는 문제다. 이전에 풀었던 안전영역(2468) 문제의 경우 최저 높이와 최대 높이의 차이만큼 BFS를 수행했다면 이번에는 전체 n개의 빈공간중 3개를 골라 벽을 세우고 BFS를 수행해야 하므로 nC3번 만큼 BFS를 수행하게 된다. n이 커지게 되면 BFS를 수행하는 횟수도 같이 커지게 된다. 단 이 문제에서는 연구소의 넓이가 8 X 8이고 최소 2개의 바이러스가 존재하기 때문에 빈공간의 최대 개수는 62가 된다. 즉 최대 62C3 = 37820 번 만큼 BFS를 수행하게 된다. 시간제한이 2초이기 때문에 37820번 BFS를 수행해도 시간초과가 나지는 않을 것이다.

수행해야할 BFS는 굉장히 간단하다. 이전에 토마토 문제에서 익은 토마토가 주변에 안익은 토마토를 익게 만들 때 사용했던 BFS를 그래도 사용하면 된다. 아마 BFS는 토마토보다 쉬울것 같다. 토마토에 관한 게시글은 여기에서 확인할 수 있다.

먼저 연구소 정보를 입력받으면 빈공간에 대한 정보를 따로 저장해 놓는다. 이후 조합을 만드는 함수를 이용하여 여러개의 빈공간중 3개를 선택하고, 선택된 시점에서 BFS를 수행하여 감염되지 않은 공간의 넓이를 구한다. 감염되지 않은 공간의 넓이 중 가장 큰 값을 출력한다.

이 문제는 단순 BFS를 사용하던 것에서 조합을 추가해서 문제를 풀어야 한다는 특징이 있다. 지금까지 단순히 BFS를 수행하면 문제가 풀렸던 것과는 다르다고 생각한다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)