이 문제는 3가지 단계로 풀면된다
(1) 벽을 3개 세우기
(2) DFS 나 BFS로 바이러스 퍼뜨리기
(3) 안전영역 카운트하기
N,M이 모두 최대 8이다. 그렇기때문에 최악의 경우, 공간은 최대 64개이다.
64C3으로 조합을 통해 벽을 세우면 -> 21504번 반복
(이때 중요한 점은, 벽은 바이러스와 벽이 없는 곳에만 세울 수 있다. 즉, 현재 맵 사응로 0인 부분에만 벽을 세울 수 있다)
각 반복마다 DFS나 BFS로 바이러스 퍼뜨리면 -> 64번 반복
안전 영역 카운트하면 -> 64번 반복
총 반복 횟수는 21504*(64+64) = 2,752,512 로 연산량은 충분하다.
1. 풀이
#include <bits/stdc++.h>
using namespace std;
int a[8][8];
int visited[8][8];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int n,m;
vector<pair<int,int>> virus_list;
vector<pair<int,int>> wall_list;
void dfs(int y, int x) {
visited[y][x]=1;
for(int i=0;i<4;i++) {
int ny=y+dy[i];
int nx=x+dx[i];
if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
if(visited[ny][nx]) continue;
if(a[ny][nx]==0) dfs(ny,nx);
}
return;
}
int main() {
cin >> n >> m;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
cin >> a[i][j]; //연구소 초기 모습을 2차원 배열에 저장
if(a[i][j]==2) virus_list.push_back({i,j});
else if(a[i][j]==0) wall_list.push_back({i,j});
}
}
int ret=-1; //MAX찾기위해 결과값의 초기값을 -1로 설정
for(int i=0;i<wall_list.size();i++) {//O(64C3*(4*64))
for(int j=i+1;j<wall_list.size();j++) {
for(int k=j+1;k<wall_list.size();k++) {
int cnt=0; //안전 영역을 카운트할 카운트 변수
fill(&visited[0][0], &visited[0][0]+64, 0); //visited를 초기화
a[wall_list[i].first][wall_list[i].second]=1;
a[wall_list[j].first][wall_list[j].second]=1;
a[wall_list[k].first][wall_list[k].second]=1;//a에 벽 3개 세우기
for(int p=0;p<n;p++) {
for(int q=0;q<m;q++) {
if(!visited[p][q] && a[p][q]==2) dfs(p,q);
}
}//전염병 다 퍼뜨려서 2로 채움
for(int p=0;p<n;p++) {
for(int q=0;q<m;q++) {
if(a[p][q]==0 && !visited[p][q]) cnt++; //0인애들 카운트
}
}
ret = max (ret, cnt);
a[wall_list[i].first][wall_list[i].second]=0;
a[wall_list[j].first][wall_list[j].second]=0;
a[wall_list[k].first][wall_list[k].second]=0;
}
}
}
cout << ret;
return 0;
}
a[][]를 입력 받을때 바이러스가 존재하는 곳과 벽을 세울 수 있는(값이 0인) 지점들을 vector에 넣어서 따로 관리한다.
벽을 세울 수 있는 지점들이 저장된 wall_list 이름의 vector에서 3중 for문으로 3개를 뽑는 조합을 만든다.
각 조합에 대해서 DFS로 a[][]가 0인 노드들을 순회하며 바이러스가 퍼뜨려진 곳은 visited[][]에 1로 표시한다.(=바이러스를 퍼뜨리는 행위)
이후, 이중 for문으로 그래프를 순회하며 a[][]가 0이고, visited[][]가 0인 지점들을 찾고나서 이전에 세웠던 벽 3개를 원상 복귀 시킨다.
2. 오답 노트
(1) 거의 다 맞았는데..벽세우기 실수
기존 벽이 존재하는 지점에는 벽을 세우지 못한다는 것을 인지했는데 바이러스가 존재하는 지점에 벽을 세울 수 없다는 것을 깜빡하고 실수해서 틀렸다.
(2) 기존 코드의 비효율적 부분들
-
기존 코드에는 그래프 원본을 저장하는 2차원 배열 1개, 각 반복마다 사용하는 오염될 2차원 배열 1개를 만들어서 매 반복마다 원본 2차원 배열을 deep copy해서 사용해서 비효율적이었다. 개선된 코드에서는 배열을 1개만 사용하고 매번 원상복구 해주는 식이라서 효율적이다
-
기존 코드에서는 전염병의 방문을 a[][]를 2로 만듦으로써 표시했다. 그러나 잘 생각해보면 어차피 visited[][]로 전염병이 퍼진 곳은 확인이되기에 굳이 a[][]를 2로 만들어줄 필요가 없었다. 개선된 코드에서는 vistied[][]로 전염병이 퍼진 곳을 식별하고 a[][]는 따로 건들이지 않으므로 효율적이다.
(3) 벽 3개 세우기. 조합 어떻게 구현?
3중 for문으로 조합을 구현하는 것 까지는 떠올렸고, 기능 자체는 동작했지만 매우매우 비효율적이었다.
개선된 코드에서는 vector에 벽을 세울 수 있는 후보지들을 pair<int,int> 형태로 저장해두고 vector의 size로 index 범위를 구하여, 이를 기반으로 3중 for문을 돌려서 조합을 구현한다. 이 방식이 훨씬 더 직관적이고 코드 가독성도 좋다.
다음부터 이런식으로 2차원 여러개중에 3개를 골라야하는 경우
vector<pair<int,int>>에좌표들을 저장해두고vector의 index중 3개를 뽑는 방식을 활용해야겠다.
