myt-algorithm-practice/Samsung SW Certi Adv
[Algorithm][C++] JUNGOL 4198: swat. 산불
hotamul
2021. 11. 1. 00:11
url: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3548&sca=99
JUNGOL
www.jungol.co.kr
풀이 핵심
1. Back Tracking / Bruth Force 문제 (Blood Fill 방법? 으로 구현)
2. 초기 불 (2) 의 위치 정보를 vector fire에 저장
3. 초기 safe zone (0) 위치 정보를 vector safe_zone에 저장
4. 재귀 함수 solve 구현.
- 전달 인자는 safe_zone vector의 index와 벽을 만든 횟 수 cnt.
- 현재 index가 가르키는 safe zone을 벽으로 만들 거나 만들지 않거나 (만들지 않을 경우 cnt 는 증가 시키지 않고 index 만 증가 시켜 solve 함수 재 실행)
- cnt가 3일 경우 fire_spread 함수 실행
- fire_spread 함수가 반환한 값이 ans 보다 크면 그 값을 ans에 대입한다.
5. fire_spread 함수는 큐를 이용해 불 (2)이 번질 수 있는 곳까지 모두 번지게 만드는 함수이다.
- 먼저 초기 safe zone의 개수 (safe_zone.size() - 3, -3을 해주는 이유는 3개를 벽으로 만들었기 때문) 를 fire_spread 함수가 return 할 ret 변수에 저장하고 큐를 생성한다. 중복 방문을 방지하기 위해 visit 함수를 만들고 0으로 초기화 한다.
- 기존에 불의 위치를 저장했던 fire vector의 값들을 큐에 push 한다
- 방문하지 않았고 (아직 불이 번지지 않았고) 배열의 크기를 넘지 않는 곳에 방문하게 되면 위치 정보를 큐에 담고 visit배열에 표시 (true) 한다. 그리고 ret 을 1 감소 시킨다.
- 큐를 모두 비우고 ret을 return 한다. (남아 있는 safe_zone 개수를 return 한다)
코드
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int N, M, ans;
int map[8][8];
struct POS {
int r, c;
};
vector<POS> fire; // 초기 불 위치 정보
vector<POS> safe_zone; // 초기 safe zone 위치 정보
const int dr[] = { 0,0,-1,1 };
const int dc[] = { 1,-1,0,0 };
inline int fire_spread() { // blood fill 방법으로 불 퍼지기
int ret = safe_zone.size() - 3;
queue<POS> q;
bool visit[8][8] = { 0, };
for (int i = 0; i < (int)fire.size(); i++) {
visit[fire[i].r][fire[i].c] = true;
q.push({ fire[i] });
}
while (!q.empty()) {
POS cur = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++) {
int nr = cur.r + dr[dir];
int nc = cur.c + dc[dir];
if (nr < 0 || nr >= N || nc < 0 || nc >= M || visit[nr][nc]) {
continue;
}
if (map[nr][nc] == 0) {
ret--;
visit[nr][nc] = true;
q.push({ nr,nc });
}
}
}
return ret;
}
void solve(int cnt, int idx) { // 재귀 함수로 완전 탐색
if (idx >= (int)safe_zone.size()) return;
if (cnt == 3) {
int candi = fire_spread();
if (candi > ans) {
ans = candi;
}
return;
}
// 현재 index가 가르키는 safe zone 벽으로 만들기
map[safe_zone[idx].r][safe_zone[idx].c] = 1;
solve(cnt + 1, idx + 1);
map[safe_zone[idx].r][safe_zone[idx].c] = 0;
// 현재 index가 가르키는 safe zone 벽으로 만들지 않기
solve(cnt, idx + 1);
}
int main() {
scanf("%d %d", &N, &M);
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
scanf("%d", &map[r][c]);
if (map[r][c] == 0) {
safe_zone.push_back({ r,c });
}
else if (map[r][c] == 2) {
fire.push_back({ r,c });
}
}
}
solve(0, 0);
printf("%d", ans);
return 0;
}