14502 연구소

BOJ::14502 연구소

https://www.acmicpc.net/problem/14502

1. 2차원 배열에서 백트래킹을 통해 벽을 세우는 모든 경우에 대해 탐색.

2. 벽을 3개 세웠으면 바이러스를 퍼뜨림.

3. 안전영역 갯수를 카운팅.

4. 최대값 출력.

#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
 
int n, m, res;
int map[8][8];
bool visited[8][8];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
void spread_virus(int x,int y) {
    visited[x][y] = true;
 
    for (int i = 0; i < 4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
        if (ax >= 0 && ay >= 0 && ax < n&&ay < m && !visited[ax][ay] && map[ax][ay] == 0) {
            spread_virus(ax, ay);
        }
    }
}
 
void get_result() {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0 && !visited[i][j]) ans++;
        }
    }
    res = max(res, ans);
}
 
void dfs(int x,int y,int cnt) {
    map[x][y] = 1;
 
    //벽 3개 세움
    if (cnt == 3) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 2) spread_virus(i, j);
            }
        }
 
        get_result();
        memset(visited, 0, sizeof(visited));
    }
    else {
        //같은라인
        for (int i = y+1; i < m; i++) {
            if(map[x][i]==0) dfs(x, i, cnt + 1);
        }
        //다음라인부터
        for (int i = x + 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(map[i][j] == 0) dfs(i, j, cnt + 1);
            }
        }
    }
 
    map[x][y] = 0;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0)    dfs(i, j, 1);
        }
    }
    
    cout << res << endl;
}

------- 예전에 풀었던 방법 ---------

처음 벽을 세우는 경우에 대해 신박한 방법 없나? 라는 생각을 가지고 열심히 생각해봤지만....

벽을 3개 세울 수 있는 모든경우에 대해 찾아보는거 말고는 방법이 떠오르지 않았다.

그래서 벽을 3개 세울 수 있는 모든 경우에 대해 벽을 세워보고 안전지역 개수를 카운팅하여 풀었다.

보통 map 배열을 2차원으로 놓는데, 2차원으로는 어떤식으로 3개를 놓아야 할지 모르겠어서

map 을 1차원으로 두고 백트래킹 하여 풀었다. 

n x m 배열에서 2차원처럼 인덱싱 할때는 map[ i / m ][ i % m ] 을 이용하면 된다.

#include <stdio.h>
#include <memory.h>
 
int n, m, res;
int map[8*8];
int visited[8][8];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
int getSafetyZone() {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i*m + j] == 0 && !visited[i][j]) {
                cnt++;
            }
        }
    }
    return cnt;
}
 
void spreadVirus(int x,int y) {
    for (int i = 0; i < 4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
        if (ax >= 0 && ay >= 0 && ax < n&&ay < m) {
            if (!visited[ax][ay] && map[m*ax+ay] == 0) {
                visited[ax][ay] = true;
                spreadVirus(ax, ay);
            }
        }
    }
}
 
void solve(int v, int cnt) {
    //벽 세우기
    map[v] = 1;
 
    //벽을 3개 세웠으면 카운팅
    if (cnt == 3) {
        memset(visited, 0, sizeof(visited));
        //바이러스 퍼뜨리기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[m*i + j] == 2) {
                    spreadVirus(i,j);
                }
            }
        }
        //안전지역 갯수 세기
        int cnt=getSafetyZone();
        if (res < cnt) {
            res = cnt;
        }
    }
    else {
        for (int i = v + 1; i < n*m; i++) {
            if (map[i] == 0) {
                solve(i, cnt + 1);
            }
        }
    }
 
    map[v] = 0;
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i*m + j]);
        }
    }
 
    for (int i = 0; i < n*m; i++) {
        if (map[i] == 0) {
            solve(i, 1);
        }
    }
    printf("%d\n", res);
}