[백준 #14502 c++] 연구소

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

14502번: 연구소

 

dfs를 통한 완전탐색이다.

완전탐색인지를 알아차리는 것이 중요하기 때문에 시간복잡도 계산하는 연습을 꾸준히 해두어야 한다.

 

세로길이 m, 가로길이 n인 배열에서 벽 3개를 세우는 경우의 수는 총 m x n 개에서 3개를 택하는 조합과 같다.

그렇게 벽이 세워진 상황에서 배열의 모든 공간을 하나씩 탐색하는 경우의 수는

 

{mn * (mn - 1) * (mn - 2) / (3 * 2 * 1)} * mn

 

이 된다.

여기서 m과 n의 최대값인 8을 넣으면

 

(64 * 56 * 48 / 6) * 64 = 1,835,008 이 나온다. (실제로는 예외처리가 들어가기 때문에 더 적게 나온다.)

 

즉, 완전탐색으로 풀어도 전혀 문제없을 만큼의 시간복잡도이다.

 

 

이제 문제를 풀어보자.

dfs 탐색인건 알겠고, 그럼 어떻게 접근할까?

 

벽을 반드시 3개 세워야 하므로 벽의 위치를 a, b, c라고 하자.

각 a, b, c 상황에서 바이러스의 위치부터 탐색하여 빈 공간을 바이러스로 뒤덮은 다음

빈 공간의 개수를 세는 것이 괜찮아보인다.

 

하지만 이 경우 바이러스로 뒤덮기 전과 후의 공간이 나뉘어져야 한다.

그래서 대신 바이러스로 뒤덮지 말고

빈 공간부터 탐색하여 바이러스를 만나는 경우에는 그 dfs로 세어진 개수는 무효화하는 식으로 바꿔볼 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n, m;
int cnt = 0;
bool meetVirus = false;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool visit[9][9];
bool wall[9][9];
int lab[9][9];

void dfs(int y, int x) {
    visit[y][x] = true;
    cnt++;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
        if (lab[ny][nx] == 2) {
            meetVirus = true;
        }
        if (!visit[ny][nx] && !wall[ny][nx] && lab[ny][nx] == 0) {
            dfs(ny, nx);
        }
    }
}

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 >> lab[i][j];
        }
    }

    int ans = 0;
    for (int a = 0; a < n * m; a++) {
        if (lab[a / m][a % m]) continue;
        for (int b = a + 1; b < n * m; b++) {
            if (lab[b / m][b % m]) continue;
            for (int c = b + 1; c < n * m; c++) {
                if (lab[c / m][c % m]) continue;

                wall[a / m][a % m] = true;
                wall[b / m][b % m] = true;
                wall[c / m][c % m] = true;

                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        if (!visit[i][j] && !wall[i][j] && lab[i][j] == 0) {
                            int tmp = cnt;
                            dfs(i, j);
                            if (meetVirus) cnt = tmp;
                            meetVirus = false;
                        }
                    }
                }
                ans = max(ans, cnt);

                cnt = 0;
                wall[a / m][a % m] = false;
                wall[b / m][b % m] = false;
                wall[c / m][c % m] = false;
                fill(&visit[0][0], &visit[8][9], 0);
            }
        }
    }

    cout << ans;

    return 0;
}