[BOJ] 14502 : 연구소

14502 : 연구소

풀이

조합 BFS

삼성기출 변형문제

전형적인 삼성SW역량테스트 문제이다.

벽을 3개 세울수 있는 모든 경우 조합을 짠뒤, 가스가 이동할 수 있는 곳을 BFS로 탐색하면 된다.

그리고도 남은 0의 개수를 세서, 최대의 0이 남는 경우가 정답이다.

조합 짜는 부분을 첫번째는 매개변수 1개를 인덱스로 넘겨서 이렇게 짜고,(본문 코드)

int x = idx / m;
int y = idx % m;
if (arr[x][y] != 0) {
        go(idx + 1, cnt);
    }
    else {
        arr[x][y] = 1;
        go(idx + 1, cnt + 1);
        arr[x][y] = 0;
        go(idx + 1, cnt);
    }

두번째는 sx,sy를 넘겨가면서 2중반복문으로 이렇게 짰다.

시간은 동일하다.

for (int i = sx; i < n; i++) {
        for (int j = sy; j < m; j++) {
            if (arr[i][j] == 0) {
                arr[i][j] = 1;
                go(i, j, cnt + 1);
                arr[i][j] = 0;
            }
        }
        sy = 0;
    }

코드

#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
//0:빈칸 1:벽 2:바이러스
int arr[8][8];
int arr2[8][8];
int ans = 0;
const int dx[] = { -1,0,1,0 };
const int dy[] = { 0,1,0,-1 };
queue<pair<int, int>> virus;
void go(int idx, int cnt) {
    if (cnt == 3) {
        int sum = 0;
        memcpy(arr2,arr,sizeof(arr));
        queue<pair<int, int>> q = virus;
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (arr2[nx][ny] == 0) {
                        arr2[nx][ny] = 2;
                        q.push({ nx,ny });
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //cout << arr2[i][j]<<' ';
                if (arr2[i][j] == 0)
                    sum++;
            }
            //cout << '\n';
        }
        if (sum > ans)
            ans = sum;
        return;
    }

    if (idx >= n*m) {
        return;
    }

    int x = idx / m;
    int y = idx % m;
    if (arr[x][y] != 0) {
        go(idx + 1, cnt);
    }
    else {
        arr[x][y] = 1;
        go(idx + 1, cnt + 1);
        arr[x][y] = 0;
        go(idx + 1, cnt);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //벽을 3개 세울수 있을때 최대 안전영역 찾기
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 2) {
                virus.push({i,j});
            }
        }
    }
    go(0,0);
    cout << ans;
    return 0;
}
Written on April 12, 2019