문제링크 : https://www.acmicpc.net/problem/14502
문제설명
.
예전에 이 문제를 처음 봤을당시, 어떻게 풀어야할지 몰라 미루고 있었다가, n퀸, 2048 같은 백트래킹 문제를 접하고 나서야 이 문제가 백트래킹이 필요한 문제인지 알아차렸다.
풀이
일단 나는 DFS를 통해 맵에 벽을 세우는 조합을 만들었고, 벽은 3개를 반드시 설치해야하기 때문에, 벽 3개를 세운 조합 하나가 완성되면, 바이러스를 퍼트리고 (바이러스를 퍼트리는 부분은 bfs방식을 사용했다.) 안전지대가 얼마나 있는지 체크한다. 그 다음 다른 조합들과 비교하며 안전지대가 가장 많이 생기는 경우를 찾는 식으로 코드를 구성했다
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int a, b; int map[9][9]; int tempmap[9][9]; int maxx = 0; bool used[9][9]; vector<pair<int,int> >virus; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; void clear() // 배열 초기화 해주는 함수 { for (int i = 1; i <= a; i++) { for (int j = 1; j <=b; j++) { tempmap[i][j] = map[i][j]; used[i][j] = false; } } } int check() // 바이러스 없는땅 갯수 return { int sum = 0; for (int i = 1; i <= a; i++) { for (int j = 1; j<= b; j++) { if (tempmap[i][j] == 0) { sum++; } } } return sum; } void bfs() // 바이러스 퍼지게하는 함수 { clear(); queue<pair<int,int> >q; for(int i = 0; i < virus.size(); i++) // 처음에 좌표입력 받을 때 바이러스 위치 기억해둔거 q에 넣기 { q.push(make_pair(virus[i].first,virus[i].second)); used[virus[i].second][virus[i].first] = true; } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i< 4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx >=1 && xx <= b && yy >= 1 && yy <= a && !used[yy][xx] && tempmap[yy][xx] == 0) { tempmap[yy][xx] = 2; used[yy][xx] = 1; q.push(make_pair(xx,yy)); } } } } void dfs(int now,int x, int y) // dfs로 벽 조합 만들기 { if (now == 3) // 벽이 3개 만들어지면 바이러스 퍼트려서 안전한곳 몇개인지 체크 { bfs(); maxx = max(maxx,check()); return ; } for (int i = 1; i <= a; i++) { for (int j = 1; j <= b; j++) { if (map[i][j] == 0) { map[i][j] = 1; dfs(now+1,j,i); map[i][j] = 0; } } } } int main() { cin >> a >> b; for (int i = 1; i <= a; i++) { for (int j =1 ;j <= b; j++) { cin >> map[i][j]; if (map[i][j] == 2) // 바이러스 위치 벡터에 입력하기 virus.push_back(make_pair(j,i)); } } dfs(0,1,1); cout << maxx; return 0; } | cs |
