문제 링크입니다: https://www.acmicpc.net/problem/17142
17142번: 연구소 3
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 모두 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는
www.acmicpc.net
브루트포스 + next_permutation을 이용하면 간단하게 풀 수 있는 문제였습니다.
알고리즘은 아래와 같습니다.
1. 연구소를 입력받을 때 바이러스의 좌표를 virus 벡터에 추가해줍니다.
2. temp 벡터를 통해 활성화된 바이러스의 인덱스를 표시합니다.
ex) 바이러스가 9개고 활성화된 바이러스가 3개라면 000000111과 같이 표시하여 마지막 3개 바이러스가 활성화되었다고 표시
ex) 비슷한 맥락으로 110100000의 경우 앞에 두개와 네 번째 바이러스가 활성화되었다고 표시
3. 현재 벽도 바이러스도 아닌 칸의 개수를 파악해서 DFS 함수에 매개변수로 전달합니다.
4. DFS 함수에서 temp 배열을 통해 활성화된 바이러스를 큐에 넣어주고 일반적인 BFS를 수행하면 됩니다.
4.1 BFS를 수행하다가 매개변수로 전달한 칸의 개수가 0이 되면 바이러스가 전부 확산된 것이므로 BFS를 멈춘 뒤 결과를 초기화하고 다음 temp 배열에 대해 다시 3~4번을 진행하면 됩니다.
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 17144번 미세먼지 안녕! (5) | 2019.05.09 |
|---|---|
| 백준 17143번 낚시왕 (4) | 2019.05.09 |
| 백준 17140번 이차원 배열과 연산 (2) | 2019.05.08 |
| 백준 12904번 A와 B (0) | 2019.05.06 |
| 백준 8982번 수족관 1 (3) | 2019.05.06 |