[백준] 14502 연구소

14502번: 연구소

 

www.acmicpc.net

풀이

DFS와 BFS를 활용해서 해결하였다. 백트래킹으로 모든 경우의 벽을 세워보고, 벽을 3개 세웠을 경우에 BFS를 통해 빈 칸의 최대 넓이를 구하면 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, blank, ans;
int map[8][8];
vector<pair<int, int>> virus;
vector<pair<int, int>> blanks;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

int bfs(int count) {
    bool visited[8][8] = { false, };
    queue<pair<int, int>> q;
    // 큐에 바이러스를 모두 넣는다
    for (auto v : virus) {
        visited[v.second][v.first] = true;
        q.push(v);
    }

    while (!q.empty()) {
        int x = q.front().first; int y = q.front().second;
        q.pop();

        if (count < ans) return -1;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; int ny = y + dy[i];
            if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1) continue;
            if (!visited[ny][nx] && map[ny][nx] == 0) {
                count--;
                q.push({ nx, ny });
                visited[ny][nx] = true;
            }
        }
    }
    return count;
}

void dfs(int idx, int cnt) {
    // 벽 3개를 다 세운 경우
    if (cnt == 3) {
        // 벽을 3개 세웠으므로 blank -3
        ans = max(ans, bfs(blank - 3));
        return;
    }

    // 백트래킹하면서 벽을 세운다
    for (int i = idx + 1; i < blanks.size(); i++) {
        int x = blanks[i].first; int y = blanks[i].second;
        map[y][x] = 1;
        dfs(i, cnt + 1);
        map[y][x] = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 0) {
                // 빈 칸 개수 미리 카운팅
                blank++;
                // 빈 칸 위치 저장
                blanks.push_back({ j, i });
            }
            // 바이러스 위치 저장
            if (map[i][j] == 2) virus.push_back({ j, i });

        }
    }
    dfs(-1, 0);
    cout << ans << '\n';
    return 0;
}