BOJ 14502 연구소

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

14502번: 연구소

#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdint>

int N,M,dx[]={0,1,0,-1}, dy[] = {1,0,-1,0},min = INT32_MAX,max = 0,wall=0;

inline bool bound(int r,int c) {return r<N&&r>=0&&c<M&&c>=0;}
std::queue<std::pair<int,int>> ori_Q;

void mk_wall(short a[],int wall) {
    int cnt = 0;
    if(depth >= 3) { // 벽 3개를 세웠으면
        short cp[N*M]; // 현재 연구소 상태를 복사할 배열
        memcpy(cp,a,sizeof(cp));
        int r=0,c=0;
        
        std::queue<std::pair<int,int>> Q(ori_Q);

        while(!Q.empty()) { // 바이러스가 침투할 수 있는 공간 채우기
            r = Q.front().first, c = Q.front().second;
            Q.pop();
            for(int i=0;i<4;++i) {
                int n_r = r+dy[i], n_c = c+dx[i];
                if(!bound(n_r,n_c)||cp[(n_r)*M+n_c] != 0) continue;
                Q.push({n_r,n_c});
                cp[(n_r)*M+n_c] = 2;
            }
        }
        for(int i=0;i<N*M;++i)
            if(cp[i] == 0) cnt++; // 안전한 공간 세기
    	if(cnt > max) max = cnt;
    	return;
    } // end of if
    else  {
        for(int i=0;i<N*M;++i) {
            if(a[i] != 0) continue;
            a[i] = 1; // 벽 세우기
            mk_wall(a,wall+1);
            // backtrack된 위치
            a[i] = 0; // 탐색한 위치 벽 제거
        }
    }
}
int main() {
    scanf("%d%d",&N,&M);
    short a[N*M];
    for(int i=0;i<N*M;++i) {
        scanf("%hd",&a[i]);
        if(a[i] == 2) ori_Q.push({i/M,i%M}); // 바이러스의 위치 큐에 추가
    }
    mk_wall(a,0);
    printf("%d",max);
}

모든 벽을 세울 수 있는 경우에 대해 벽을 세운 후 탐색해 최대 안전 영역 넓이를 구하는 문제이다. 문제의 조건 

지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

을 제대로 확인하지 않고 무턱대고 시작한 바람에 map 배열이 1차원으로 돼 있는 등 코드 가독성 부분에서 아쉬운 부분이 있다. 

 

재귀 호출을 통해 벽을 설치 가능한 모든 경우에 대해 벽을 하나씩 세운다. 깊이가 3이면(벽을 다 세웠으면) 안전 영역의 넓이를 계산하고, 빠져나와 다음 경우(벽을 세우는 경우)를 살펴본다. 

 

채점 후 다른 분들의 코드를 잠깐 살펴보니, dfs를 이용한 탐색도 있었지만, 재귀를 이용하는 방법이 조금 깔끔한 편이었다.