[백준] 14502번 연구소

문제 정의

벽을 3개 세워서 연구소의 바이러스(2)가 최대한 작게 퍼지도록 하여서, 안전영역 크기의 최대값을 구하는 문제이다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14502)

문제 풀이 

이 문제도 저번에 풀다가 실패해서 며칠만에 다시 푸는 문제다. 지도의 크기는 8*8보다 작으므로 3개의 벽을 모두 세워보고 바이러스가 퍼지지 않는 안전 영역을 구해서 최대값을 갱신하도록 한다. 이 문제는 꽤 오래전에 풀었던 문제라서 DFS를 잘 활용하지 못해서 못풀었던 것 같기도하고.. 벽을 세운다음 바이러스를 퍼지게하고, 그 때마다 안전영역의 크기를 구하도록 구현한다.  

몇시간을 잡고 있었는데 벽을 세우는 DFS를 완전히 구현하지 못했다. 내가 생각하는 로직으로는 구현이 잘 안되는데 인터넷에 푼 사람들 코드를 보면 나랑 비슷한 방법으로 구현을 해놨다. 그래서 결국 경우의 수를 구하기 위해 벡터를 사용해서 다른 방법 코드를 참고해서 구현했다. 벡터에 0, 2인 좌표들을 저장해서 3개의 벽을 세우는 경우를 for문으로 만들고, 바이러스인 2를 퍼트리는 것은 DFS를 사용해서 인접한 0을 전부 2로 바꿔주었다. 문제를 풀긴했으나 이전에 풀었던 코드에 어떤 문제가 있었는지 맑은 정신일 때 다시 한번 봐야겠다.

코드

int main()

{

int i, j, k;

val = -1;

scanf("%d %d", &N, &M);

for(i=0; i<N; i++){

for(j=0; j<M; j++){

scanf(" %d",&wall[i][j]);

visited[i][j]=0;

virusVisit[i][j]=0;

if(wall[i][j] == 0)

zero.push_back(make_pair(i,j));

else if(wall[i][j] == 2)

two.push_back(make_pair(i, j));

}

}

for(i=0; i<zero.size()-2; i++)

{

for(j=i+1; j<zero.size()-1; j++)

{

for(k=j+1; k<zero.size(); k++)

{

wall[zero[i].first][zero[i].second] = 1;

wall[zero[j].first][zero[j].second] = 1;

wall[zero[k].first][zero[k].second] = 1;

cal();

wall[zero[i].first][zero[i].second] = 0;

wall[zero[j].first][zero[j].second] = 0;

wall[zero[k].first][zero[k].second] = 0;

}

}

}

printf("%d\n", val);

}

void cal()

{

int i, j;

int result =0; 

for(i=0; i<N; i++)

for(j=0; j<M; j++)

copyw[i][j] = wall[i][j];

for(i=0; i<N; i++){

for(j=0; j<M; j++){

if(copyw[i][j] == 2){

checkVirus(i,j);

}

}

}

for(i=0; i<N;i++){

for(j=0; j<M; j++){

if(copyw[i][j] == 0)

result++;

}

}

val = max(val, result);

}

void checkVirus(int x, int y)

{

int i;

virusVisit[x][y]=1;

copyw[x][y] = 2;

for(i=0;i<4; i++)

{

if(copyw[x+idx[i]][y+idy[i]] != 0 || x+idx[i] < 0 || x+idx[i] >= N ||

y+idy[i] < 0 || y+idy[i] >= M)

continue;

checkVirus(x+idx[i],y+idy[i]);

}

virusVisit[x][y]=0;

}