[Algorithm][C++] JUNGOL 4198: swat. 산불

url: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3548&sca=99 

JUNGOL

 

풀이 핵심

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;
}