https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
www.acmicpc.net
이차원 배열을 통해서 map을 그리고 벽을 3개만 칠 수 있는데 벽을 3개를
쳤을 때 안전영역(바이러스가 퍼지지않는) 을 최대로 만들어 그 최대값을 출력하는 문제입니다.
초반에 어떠한 규칙을 세워야 좋을까 생각이 들었지만 너무 경우의 수가 많아 딱히
적용되는 규칙을 찾기 힘들어 모든 경우의 수를 다 세우고 그 경우의 수에 따라서 안전영역의 값을
구해 봐야되나....? 라는 생각을 한후 그럴경우 입력값의 조건들이 너무 크면 안되기 때문에 그를
확인해보니 (3<=N.M<=8) 이라 작은값임을 확인하고 그로 방향을 잡아 풀었습니다.
저는 [10][10] 배열을 만들어 index 0과9는 1로 채워서 벽같은 느낌을 주었습니다(바이러스가 퍼지지 못하게)
물론 조건문에 index를 걸어도 되지만 귀찮아서.....
아 그리고 벽이 세워질 수 있는 지역은 좌표를 구조체로 설정하여
벡터(vector)에다가 모두 넣은 다음 그 벡터에서 3개씩을 골라서 그 3개에 벽이 세워졌을 때 안전구역을 구하였습니다.
bfs를 통해서 -- 더이상 바이러스가 퍼질 구역이 없어서 큐가 비어있게 될경우 탐색을 멈춤
3중 반복문 이용(완전탐색) -- 이 과정에서 조건수정을 하느라고 시간이 좀 걸렸습니다.
<코드>
