[백준] 연구소 14502

한동안 알고리즘을 하느라 블로그 글을 쓰지 못했다ㅠ

오늘부터는 알고리즘 풀이에 대한 글도 써보려고 한다ㅎㅎ

 그 첫 번째 문제는 연구소이다. 백준 홈페에지( https://www.acmicpc.net/ )에 가면 누구나 풀어볼 수 있다.

연구소 14502 https://www.acmicpc.net/problem/14502

알고리즘을 시작한지 얼마안되서 역시나 풀이가 어색할 수도 있다ㅎㅎ

포너블과는 다른 매력이 있는 것 같다. (개인적으로는 포너블이 더 즐거움)

문제는 다음과 같다.

N x M으로 이루어진 지도가 있고 그 곳에는 바이러스와 벽, 그리고 공간이 있다.

바이러스는 벽이아닌 공간으로 점차적으로 퍼져나가는데 우리는 3개의 벽을 세울 수 있다.

이 때 세우는 3개의 벽 3개는 꼭 세워야 한다. 여기까지 문제를 읽었을 때

우선적으로 N과 M의 크기가 8이라는 아주 작은 수여서

 Brute force와 순열 그리고 BFS를 사용하면 풀 수 있을 것 같았다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <unistd.h>
using namespace std;
 
 
int map[8][8];
int check[8][8];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int copymap[8][8];
int n, m;
 
int main()
{
    int wall_space=0;
    queue<pair<int,int>>q;
    cin >> n >> m;
    for(int y=0; y<n; y++){
        for(int x=0; x<m; x++){
            cin >> map[y][x];
            if(map[y][x]==2){
                check[y][x]=2;
            }
            if(map[y][x]==0)
                wall_space++;
        }
    }
 
    int *wall= new int[wall_space];
    memset(wall,0,wall_space);
    for(int i=0; i<3; i++)
        wall[i]=1;
 
    int MAX=-99999999;
    int idx=0;
    do{
        int sum=0;
        memcpy(copymap,map,sizeof(map));
        memset(check,0,sizeof(check));
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(copymap[i][j]==0){
                    copymap[i][j]=wall[idx];
                    idx++;
                }
                for(int i=0; i<n; i++){
                    for(int j=0; j<m; j++){
                        if(copymap[i][j]==2){
                            q.push(make_pair(i,j));
                            check[i][j]=2;
                        }
                    }
                }
                if(idx==wall_space){
                    idx=0;
                    while(!q.empty()){
                        int cur_y = q.front().first;
                        int cur_x = q.front().second;
                        q.pop();
 
                        for(int z=0; z<4; z++){
                            int nx = cur_x + dx[z];
                            int ny = cur_y + dy[z];
                            if(0<=nx && nx<m && 0<=ny && ny<n && check[ny][nx]==0 && copymap[ny][nx]==0){
                                check[ny][nx]=8;
                                q.push(make_pair(ny,nx));
                            }
                        }
                    }
                    for(int v=0; v<n; v++){
                        for(int u=0; u<m; u++){
                            if(copymap[v][u]==0 && check[v][u]==0)
                                sum++;
                        }
                    }
                    MAX=max(sum,MAX);
                    break;
                }
            }
        }
    }while(prev_permutation(wall, wall+wall_space));
    cout << MAX << endl;
    delete [] wall;
    return 0;
}
 

코드의 효율이 떨어질 수도 있지만ㅎㅎ 일단 풀었다는 것에 의의를 두겠다.

코드는 보통의 BFS풀이와 같지만 우리는 무조건 3개의 벽을 세워야한다. 

그러므로 이 3개의 벽이 세워질 수 있는 모든 경우의 수를 확인해보았다.

순열을 이용했고 모든 경우의 수를 체크했을 때의 공간이 가장 많은 경우를

뽑아냈다. 굉장히 간단한 원리로 풀이가 가능했다.

copymap배열을 이용한 이유는 기존의 map을 변조하지 않고

복사본을 이용해서 변화를 진행하여 최대값을 뽑아내고 다시 돌아가서

원본을 다시 복사하여 최대값을 뽑아내도록 반복하기 위해서 사용했다.

생각보다 재미있는 것 같다ㅎㅎ 스트레스를 좀 많이 받아서 그렇지ㅎㅎ