[BOJ-14502]연구소

이문제는 보고 풀기까지 07:50 - 08:42 까지 걸렸으니, 52분 걸렸다...

그냥 보고서 DFS 네? 생각했다가 판정까지 BFS네?

생각하고 DFS, BFS를 이용하여 풀이해야 겠다고 생각을 하고 

총 과정이 3개가 필요하다고 생각했다.

과정 1 ) 완전/전체 탐색을 해서 벽3개를 세울 수 있는 모든 경우의 수를 보고

과정 2 ) BFS를 사용해서 과정 1)을 마친 경우에 맵에 있는 모든 바이러스를 퍼지게 한다.

과정 3 ) 해당 map에 안전 영역 수를 계산한다.

그리고 코드를 작성하였다. 

실수 1 ) BFS 문제에서 나는 dr, dc ; direct row, col 로 사용하는데 이걸 바보같이 대각선으로 설정해두고 값이상하다고 그러고 있었다.

바로 알아채서 바로 고치긴 했는데... 멍청이

실수 2 ) VI map[] 을 함수 인자로 넘겨줄 때 벡터기 때문에 그대로 넘겨준다는 것을 생각 못했다. 

바보짓.........

​

그리고는 실수 한 건 없던 것 아 하나 더 있다.

실수 3 ) 이것도 run 하고 바로 발견해서 다행인데.. dfs 함수 return 선언이 부족했다..... 빠가​

#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<cmath>
using namespace std;
 
typedef vector<int> VI;
VI imap[8];
int row, col; // global var
 
int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1 ,0, 0 };
 
int virus_bfs(VI dfsmap[]) {
    queue<pair<int, int> > Q;
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            if (dfsmap[r][c] == 2) Q.push(make_pair(r, c));
        }
    }
 
    while (!Q.empty()) {
        pair<int, int> here = Q.front(); Q.pop();
        int here_row = here.first;
        int here_col = here.second;
        for (int i = 0; i < 4; i++) {
            if (0 <= here_row + dr[i] && here_row + dr[i] < row &&
                0 <= here_col + dc[i] && here_col + dc[i] < col) {
                if (dfsmap[here_row + dr[i]][here_col + dc[i]] == 0) {
                    dfsmap[here_row + dr[i]][here_col + dc[i]] = 2;
                    Q.push(make_pair(here_row + dr[i], here_col + dc[i]));
                }
            }
        }
 
    }
 
    int ans = 0;
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            if (dfsmap[r][c] == 0) ans++;
        }
    }
    
    return ans;
} // 과정 2: 벽을 3개 생성을 완료한 후 바이러스를 퍼트림
  // 과정 3: 과정1-2를 거친 후 안전영역의 수
 
 
 
int dfs(int rrow, int ccol, int n_wall, VI dfsmap[]) {
    int ret = 0;
    if (n_wall == 3) {
        VI bfsmap[8];
        for (int r = 0; r < row; r++) {
            bfsmap[r].resize(col);
            for (int c = 0; c < col; c++) {
                bfsmap[r][c] = dfsmap[r][c];
            }
        }
        
        return virus_bfs(bfsmap);
    }
 
    int r = rrow;
    int c = ccol;
    for (; r < row; r++) {
        if (r != rrow) c = 0;
        for (; c < col; c++) {
            if (dfsmap[r][c] == 0) {
                dfsmap[r][c] = 1;
                ret = max(ret,dfs(r, c, n_wall + 1, dfsmap));
                dfsmap[r][c] = 0;
            }
        }
    }
    return ret;
} // 과정 1: map에 벽을 생성 모든 경우의 수
 
int main() {
 
    scanf("%d%d", &row, &col);
 
    for (int r = 0; r < row; r++) {
        imap[r].resize(col);
        for (int c = 0; c < col; c++) {
            scanf("%d", &imap[r][c]);
        }
    }
 
    int ans = 0;
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            if (imap[r][c] == 0) {
                imap[r][c] = 1;                
                ans = max(ans, dfs(r, c, 1, imap));
                imap[r][c] = 0;
            }
        }
    }
 
    printf("%d", ans);
 
    return 0;
}