dfs
-
[백준] 14502. 연구소알고리즘/백준 2021. 4. 5. 01:56
문제 출처 https://www.acmicpc.net/problem/14502 문제 설명 2차원 좌표계에 벽과 바이러스가 있다. 바이러스는 확산되지만 벽은 통과할 수 없다. 3개의 벽을 더 세워서 바이러스를 최대한 억제해라. 문제 풀이 지도가 최대 8x8로 아담하다. 3개의 벽을 세울 수 있는 모든 경우의 수를 도전해봐도 충분할 것이다. 3개의 벽을 세웠다면 바이러스를 확산시키고 안전 구역을 센다. 안전 구역의 최댓값을 출력한다. 왜 모든 경우의 수를 도전해봐도 충분한가? 최악의 경우 8x8에 3개의 벽을 세울 수 있는 경우의 수는 64C3 = 41,664 이고 8x8의 지도를 41,664번 순회한다면 2,666,496회의 연산이 필요하다. 이런 식의 어림짐작으로 1억을 넘지않는다면 백준의 1초를 통과할..