백준 14502번 연구소 (삼성 SW 역량테스트 기출문제)

문제 링크: https://www.acmicpc.net/problem/14502

사용한 알고리즘: DFS, Brute Force(완전 탐색)

문제에서는 최대 8x8 그래프를 주고, 이후 각각의 지점에서 바이러스(2), 벽(1), 빈 영역(0) 에 대한 정보를 주고 있습니다.
이때 벽 (무조건)3개를 빈 영역(0)에 세워서 바이러스를 격리시켜(벽으로 막아) 바이러스가 퍼지지 않는 안전 영역을 만들고, 이렇게 만들 수 있는 최대 안전 영역의 크기를 구하라고 하고 있습니다.

기본적인 제 풀이 생각은 다음과 같습니다.
 우선 전체 영역에서 벽만을 제외한 영역의 크기를 Area 라고 했을 때 (바이러스가 있는 영역을 포함한 크기), 주어지는 그래프의 크기가 최대 8x8로 매우 작게 주어지므로,
벽 3개를 세우는 모든 경우를 다 따져보고 (Brute Force), 각 경우마다 안전 영역을 구하여,
최대 안전 영역의 값을 각 경우마다 최신화 해 주는 것입니다.
 이때 virus가 있는 영역에서부터 DFS를 사용하여 virus가 퍼질 수 있는 영역의 크기를 계산해주고 이를 Area에서 빼주는 식으로 안전영역의 크기를 계산했습니다.

저의 풀이 과정을 써보면 다음과 같습니다.

(1) 입력을 받으면서 (virus영역포함, 벽만을 제외) Area 를 계산해 주고, 벽을 세울 수 있는 빈 영역(0)을 입력 받으면, 해당 위치를 pair형태로 Wall이라는 이름의 vector안에 저장해 줍니다. 또한 virus가 있는 영역의 위치를 pair형태로 Virus라는 이름의 vector안에 저장해 주었습니다.

(2) 과정(1)에서 모아놓은 vector (Wall) 을 살펴보며 벽 3개를 추가로 세울 수 있는 모든 경우의 수를 따져봅니다. 이때 3중 for 구문을 사용하였는데, 중복을 최소화 해주기 위해 범위 설정을 다음과 같이 해주었습니다.
 처음 설치할 벽(첫번째 for구문: i)는 0 ~ Wall.size - 2 ( 첫번째 벽을 설치한 뒤, 벽 2개를 추가로 설치해야 하니 설치할 수 있는 영역을 적어도 2개는 남겨두어야 한다고 생각했습니다.)
 두번째 설치할 벽(두번째 for구문: j)는 i+1 ~ Wall.size - 1 (마찬가지로 두번째 벽을 설치한 뒤, 벽 1개를 추가로 설치해야 하니 설치할 수 있는 영역을 적어도 1개는 남겨두어야 한다고 생각했습니다.)
 세번째 설치할 벽(세번째 for구문: k)는 j+1 ~ Wall.size
로 설정해주었습니다.

(3) 벽을 설치한 후 안전영역의 크기를 계산해주었습니다. virus가 있는 영역에서 부터 virus가 퍼질 수 있는 모든 영역의 크기를 DFS로 찾아주어, 이를 Area에서 빼주는 식으로 안전영역의 크기를 구했습니다.


 문제를 푸는 알고리즘은 특별할 건 없었지만, 저에게 있어 구현이 조금 힘든 문제였습니다.