/* 바이러스 연구소 크기 엔엠, 벽의 개수는 3개, 꼭 3개를 세움니다. 0은 빈칸 1은 벽 2는 바이러스, 안전영역의 크기는 27 안전 영역의 크기를 최대로 구하는 것 벽은 빈칸에다가 만들 수 있습니다. 벽 1을 3개 놓고 dfs 재귀로 돌립니다. 바이러스 2에 대해서 완전탐색 bfs 를 돌립니다. 체크 벽 하나를 맏듭니다. 안전 영역의 크기를 최대값을 저장하는 함수를 만들도록 합니다. 맵을 복사해야할 것 같습니다. 맵을 복사 맵을 복사하는 방법이 있습니다. 맵에 대해서 어떻게 재귀를 만들 수 있을까? */ #include <iostream> #include <queue> #include <algorithm> using namespace std; #define SIZE 8 int map[SIZE][SIZE]; int map_store[SIZE][SIZE]; int check[SIZE][SIZE]; struct points { int x, y; }; queue<points> que; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int x, y, nx, ny, n,m; int wall; int maxVal; int safe_cnt; void map_copy(int (*a)[SIZE], int (*b)[SIZE]) {
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { b[i][j] = a[i][j]; } } } void problemIn() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } } void infect_virus() { while (!que.empty()) { x = que.front().x; y = que.front().y; que.pop(); for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < n && ny < m) { if (map[nx][ny] == 0 && check[nx][ny] == 0) { map[nx][ny] = 2; check[nx][ny] = 1; que.push({ nx,ny }); } } } } } void check_init() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { check[i][j] = 0; } } } void cnt_virus() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == 0) { safe_cnt++; } } } maxVal = max(maxVal, safe_cnt); } void make_wall(int depth) { if (depth == 3) {
check_init(); safe_cnt = 0; map_copy(map, map_store); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == 2 && check[i][j]==0) { que.push({ i,j }); check[i][j] = 1; infect_virus(); } } } cnt_virus(); map_copy(map_store, map); return; } else { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == 0) { map[i][j] = 1; make_wall(depth + 1); map[i][j] = 0; } } } } } void solve() { } int main(void) { problemIn(); make_wall(0); cout << maxVal << endl; return 0; } |
와우 신기하네, 이렇게 짜면 되는구나. 처음으로 기출에 대해서 스스로 짜보았습니다. 그리고 시간도 그렇게 오래 안걸리고 2시간 정도 소요되었습니다. 문제가 다소 연쇄적으로 풀어야하는 문제이기에, 이것들에 대해 명확하게 의미를 알고 디버깅 해나가면 됩니다. 오께이. 명확한 아이디어와 명확한 구현이 필수 입니다. |