백준 14502번 연구소

백준 14502번 연구소

#include <iostream>
#include <queue>
#include<stack>
#include <cmath>
#include<string>
#include<vector>
#include<algorithm>
#include <cstring> //memset
using namespace std;
 
 
int n, m;
int wall[10][10];
int test[10][10];
 
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };
 
 
 
 
//초기 연구소상태를 test배열에 대입
void Copy() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            test[i][j] = wall[i][j];
        }
    }
 
}
 
//동서남북방향으로 0이 존재하는 모든곳 2로만들어주는 
//바이러스 감염함수
void DFS(int y, int x) {
    test[y][x] = 2;
 
    for (int i = 0; i < 4; i++) {
        int nexty = y + dy[i];
        int nextx = x + dx[i];
        if (nexty >= 1 && nexty <= n && nextx >= 1 && nextx <= m) {
            if (test[nexty][nextx] == 0) {
                DFS(nexty, nextx);
            }
        }
    }
}
 
 
//test배열에서 존재하는 0의 개수를 세는 함수
int CountSafeGround() {
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (test[i][j] == 0) {
                ret++;
            }
        }
    }
    return ret;
}
 
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> wall[i][j];
        }
    }
    int ans = 0;
    Copy();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (test[i][j] == 0) {
                test[i][j] = 1;
                for (int a = 1; a <= n; a++) {
                    for (int b = 1; b <= m; b++) {
                        test[i][j] = 1;
                        if (test[a][b] == 0) {
                            test[a][b] = 1;
                            for (int y = 1; y <= n; y++) {
                                for (int x = 1; x <= m; x++) {
                                    test[i][j] = 1;
                                    test[a][b] = 1;
                                    if (test[y][x] == 0) {
                                        //중복되지 않은 3개의 벽을 고름
                                        test[y][x] = 1;
 
                                        //연구스의 바이러스를 모두 퍼뜨려줌.
                                        for (int p = 1; p <= n; p++) {
                                            for (int q = 1; q <= m; q++) {
                                                if (test[p][q] == 2) {
                                                    DFS(p, q);
                                                }
                                            }
                                        }
 
                                        //벽을 세웠을때 가장 안전한 지역이 많은 값을 ans에 저장시킨다
                                        ans = max(ans, CountSafeGround());
                                        Copy();
                                    }
                                }
                            }
                            Copy();
                        }
                    }
                }
                Copy();
            }
        }
    }
    
    cout << ans;
    
    
 
    return 0;
}

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

DFS문제였습니다. 

문제를 푸는 관건은 임의의 중복되지않은 세 좌표를 골라주는 것이였는데요.

n,m의 숫자가 매우 작아서 그냥 for문 중첩을 엄청시켜서 풀어주었습니다 ..... ㅋㅋ 다른분들은 어떻게 풀었는지 모르겠네요!