[BOJ] 백준 14502 연구소(Swift)

문제

https://www.acmicpc.net/problem/14502

풀이

접근 방법

1. 그래프에서 0 -> 1로 변경시켜주어야 하는 작업이 필요할 것
2. 0 -> 1로 3개를 변경해주어야 하는 작업이 필요하기 때문에, 0의 위치들 중에서 3개를 뽑는 조합 알고리즘의 필요성을 느낌
3. 0의 위치를 배열로 담아주어야겠다고 생각함
4. for문 3개로 0 -> 1로 바꿔주는 방법을 하려고 했지만 이 문제에서는 필요없겠지만 추후 확장성을 위해 조합알고리즘을 짜야겠다고 생각함
5. 0 -> 1로 3개를 변경했다면, 바이러스(2)에서 BFS를 수행해야겠다고 생각함
6. 2의 위치를 배열로 담아주어야겠다고 생각함
7. BFS를 수행 이후 0의 개수를 세고 max 값을 찾는다. 그리고 0 -> 1로 바꿔준 부분을 되돌려주어야 함 (백트래킹)
8. 반복..

이 문제는 n과 m이 8이하로 매우 작다.
0의 위치들 중에서 3개를 뽑는 알고리즘의 시간복잡도는 최악의 경우(0이 8 * 8이라고 가정) 64 * 63 * 62 = 25만? 정도이다.
25만 * BFS를 수행해도 충분한 시간이 될 것이라고 예상했다.

즉 이 문제는 완전탐색 문제이고, 무차별 대입을 통해 최적의 해를 구할 수 있는 문제이다.

접근과 풀이 과정은 위에 순서대로 작성하였으며 이를 토대로 코드를 구현하여 풀었다.

소스코드

후기

완전탐색 문제, 이 문제에서 n이 크다면 어떻게 풀 수 있을 지 궁금하다.