[C++] 백준 14502 연구소, Brute-Force, BFS (Gold 4)

풀이

1. 재귀를 사용해 브루트포스로 벽을 세울 수 있는 모든 경우의 수에 대해 탐색한다.

2. 벽을 3개 세웠다면 BFS 알고리즘을 돌리면서 answer를 갱신하면 된다.

리뷰

왠지 시간 초과가 날 것 같아서 다른 기법을 써야하나 했지만, 맵의 크기가 작아서 그런지 통과되었다.

BFS함수에서 2인 지역을 큐에 먼저 집어 넣었는데, 평소 습관처럼 while 문에서  visited 벡터를 먼저 체크하고 내려가다보니 nr, nc를 Queue에 추가하지 못해서 visited 벡터가 전혀 업데이트 되지 않았다. nr, nc에 대해 검사하면서 visited 처리 해주니 업데이트가 되더라. 디버깅 하면서 시간을 많이 썼다.. 하하..

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int drow[4] = {0, 1, 0, -1};
int dcol[4] = {1, 0, -1, 0};
int row, col;
int answer = 0;

void bfs(vector<vector<int>>& m)
{
    queue<pair<int, int>> q;
    vector<vector<int>> visited;
    visited = m;

    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            if (m[i][j] == 2) {
                q.push({i, j});
            }
        }
    }
    
    while (!q.empty()) {
        pair<int, int> v = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nr = v.first + drow[i];
            int nc = v.second + dcol[i];
           
            if (nr < 1 || nr > row || nc < 1 || nc > col) continue;

            if (visited[nr][nc] == 0) {
                visited[nr][nc] = 2;
                q.push({nr, nc});
            }
        }
    }

    int cnt = 0;
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            if (visited[i][j] == 0) {
                cnt++;
            }
        }
       
    }
    answer = max(answer, cnt);
    return;
}

void make_wall(vector<vector<int>>& m, int cnt)
{
    if (cnt == 3) {
        bfs(m);
        return;
    }
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            if (m[i][j] == 0) {
                m[i][j] = 1;
                make_wall(m, cnt+1);
                m[i][j] = 0;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    freopen("14502.txt", "r", stdin);

    cin >> row >> col;
    vector<vector<int>> map(row+1, vector<int> (col+1, 0));
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            cin >> map[i][j];
        }
      
    }

    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            if (map[i][j] == 0) {
                map[i][j] = 1;
                make_wall(map, 1);
                map[i][j] = 0;
            }
        }
    }

    cout << answer << endl;
    return 0;
}