#pragma warning(disable:4996) #include<iostream> #include<vector> #include<queue> #include<algorithm> #define MAX 8 using namespace std; int map[MAX][MAX]; int n, m; bool visit[MAX][MAX]; int max_value; int dx[4] = { 0, 0, 1, -1 }; int dy[4] = { 1, -1, 0, 0 }; vector<pair<int, int>> virus; void input() { scanf("%d %d", &n, &m); for(int i=0; i<n; i++) for (int j = 0; j < m; j++) { scanf("%d", &map[i][j]); if (map[i][j] == 2) virus.push_back(make_pair(i, j)); } } void copymap(int (*a)[MAX], int(*b)[MAX]) { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i][j] = b[i][j]; } int recovery(int(*a)[MAX], int(*b)[MAX]) { int ret = 0; for(int i=0; i<n; i++) for (int j = 0; j < m; j++) { if (a[i][j] == 0) ret++; a[i][j] = b[i][j]; } return ret; } void bfs() { queue<pair<int, int>> q; for (int i = 0; i < virus.size(); i++) q.push(virus[i]); while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] != 0) continue; map[nx][ny] = 2; q.push(make_pair(nx, ny)); } } } void dfs(int x, int y, int d) { map[x][y] = 1; visit[x][y] = 1; if (d == 3) { int tmp[MAX][MAX]; copymap(tmp, map); bfs(); max_value = max(max_value, recovery(map, tmp)); visit[x][y] = 0; map[x][y] = 0; return; } for(int i=0; i<n; i++) for (int j = 0; j < m; j++) { if (visit[i][j] || map[i][j] != 0) continue; dfs(i, j, d + 1); } map[x][y] = 0; visit[x][y] = 0; } void process() { for(int i=0; i<n; i++) for (int j = 0; j < m; j++) { if (map[i][j] != 0) continue; dfs(i, j, 1); } printf("%d\n", max_value); } int main() { input(); process(); return 0; } |
헤더파일 표준 iostream, vector, queue, algorithm 포함
맵의 크기 8로 하고, 이 define 을 재사용
dfs, bfs 둘 다 들어간 문제로 전형적인 틀임.
virus 를 저장하는 벡터 만들기.
copymap, recovery 만들어서 벽3개를 세운뒤 카피, 바이러스를 퍼트린 뒤 카피, 이렇게 사용하기.
bfs 의 정석 큐를 만들어서 큐가 빌때까지 와일문을 돌립니다. 큐에 처음에 하나 들어가 있어야 합니다. 그 다음에 큐로부터 x, y 값을 하나 받고, 그 값으로 4방향 다 돌리면서 q에 새로운 데이터를 저장합니다. 그리고 새로운 nx, ny 에 대해서 범위를 벗어나지 않으면 연산 처리를 합니다. 오케이.
dfs 의 틀 처음에 x, y, d 이렇게 3개의 인자를 받습니다. 그리고 x, y에 대해서 맵과 visit의 상태를 변경해줍니다. 그리고 return 하기 전에 0으로 다시 바꿔줍니다. 그리고 그 사이에 2가지 연산이 있습니다. 첫 째 return 하는 deep 이 3이 되면 처리하는 연산이 하나 있습니다. 여기서도 return 구문 전에 map 과 visit 를 다시 0으로 변경해주어야 합니다.
그리고 다음으로 for 문을 돌리면서, 방문하지도 않았으며, 맵이 0인곳에서 dfs를 하나 더 돌립니다(벽을 하나 세웁니다.) 그리고 여기서 i, j, d+1 입니다. d+1이 핵심 연산입니다. dfs 의 마지막에 return 문을 넣어주고 끝냅니다.
마지막으로 process 함수에서 맵에서 0이 아닌 곳에서 dfs를 시작합니다. void 문은 return 을 사용하지 않아도 알아서 되나봅니다. 반환값이 없어서 그런가 봅니다.
그리고 main 문을 실행해줍니다. dfs 는 d+1 연산이 어디에 들어가는지, 그리고 return 이 되는 곳이 2 번인데 처음 기저 사례와 마지막 입니다. 이때 맵과 visit 를 초기화 해주는 것이 중요합니다.