백준(BOJ) 14502번 연구소

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

14502번: 연구소

 

문제

 

(생략)

  .

  .

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

 

 

풀이 :

 

우선 0인 구간을 모두 vector<pair<int,int>> v 배열에 집어넣자. 그 후 v배열에서 3개씩만 꺼내서 1을 만들고

 

바이러스를 퍼뜨린 후 구하고자 하는 최대값을 구한다. 그리고 v배열 3개를 다시 0으로 만들어 주자.

 

예를 들면 v에 저장된 값이 0,1,2,3 이라면(실제로는 pair지만) 우리는 012 013 023 123 순으로 꺼낸 후 각각을 모두 1로

 

만들고 바이러스를 퍼뜨릴 것이다.

 

퍼뜨릴때에는 원래 영역과 복사한 영역을 만들어서 돌려주자. 이는 벽을 3개 만드는 경우가 여러 경우이기 때문에

 

원래 영역은 기준으로 나둬야 한다.