#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 copy_map(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_safe_zone() { 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; copy_map(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_safe_zone(); copy_map(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; } } } } } int main(void) { problemIn(); make_wall(0); cout << maxVal << endl; return 0; } |
문제에 대해서 보고, 모든 경우의 수에 따라 만들어야 하는 함수를 적어둡니다. 그리고 어느 때에 어디서 사용할지 명확히 하도록 합니다. 먼저 벽을 세우는 함수 입니다. 여기서 벽이 3개가 되었을때 체크 배열을 초기화하고 안전한 지역 카운트 변수를 초기화하고 맵이 변경되므로 맵이 변경 이전에 대해서 저장을 해둡니다. 그리고 2이고 체크가 0인것에 대해서 큐에 넣고 바이러스를 퍼트립니다. 그리고 돌아왔을 때, 안전한 지역을 셉니다. 그리고 다시 저장했던 맵에 대해서 돌려둡니다. 그리고 dfs 이기에 리턴을 넣어줍니다. 오께이. 모든 바이러스에 대해 퍼트린 다음에 결과를 돌리고, 오께이. 순서를 명확히 합니다. 다음으로 엘스 구분에서는 맵이 0 인 곳을 찾아서 1을 넣고 뎁스를 넣고, 0을 다시 돌려놓는 것이 핵심입니다. 전에는 맵에서 1로 변경한 뒤에 0으로 변경하지 않았기 떄문에 그곳에서 부터 틀렸습니다. 하나를 완벽하게 구현하고도 다음 단계로 넘어가는데 문제가 됩니다. 조기화와 카운트에 대해서는 오께이 알겠습니다. 이것을 두개 결합가능합니다. 8*8 64의 연산이므로 무리가 되지 않습니다. 바이러스를 퍼치는 것을 큐오 bfs 알고리즘을 사용합니다. 처음 하나에 대해서 xy를 넣고 그것을 큐팜하고 4가지 방향에대해서 처리를 한다음에 다음 단계로 넘어가도록 합니다. 엑스와 엔에스를 연결하는 것은 시작할때 뿐입니다. 제일 아래에서 연결하지 않습니다. |