[삼성 기출 문제] 백준 14502 연구소

문제 링크

클릭시 이동합니다.

어떻게 풀까?

문제를 크게 2 부분으로 나눠야 합니다.

1. 벽을 3개 세우는 부분

2. 바이러스를 퍼뜨리는 부분 

1번은 dfs를 이용해서 조합을 이용해서 해당 좌표에 벽을 세운다 or 안세운다 의 동작을 통해서 모든 구역에 벽을 3개씩 세워보는 방법을 이용합니다.

그리고 벽을 3개 세웠을 때, bfs를 이용해서 2번을 동작해서, 바이러스의 개수를 세서 이 최댓값을 출력하면 풀이는 완료됩니다!

2차원에서 조합을 이용하는 방법을 알아봅시다! n = 3이라고 하겠습니다. 시작은 (0,0) 입니다.

우선, (0,0)에 벽을 세울지 안 세울지 정합니다. 우선 세운다고 가정하겠습니다.

그럼, 열의 크기를 1 늘려준 뒤에 해당 위치에서 다시 위의 과정을 반복합니다.

이번에는 안세운다고 하겠습니다. 다시 다음 벽을 정합니다. 열의 크기를 1 늘려서 (0,2)를 봅니다.

해당 위치에 벽을 세운다고 한다면, 이제 다음 벽은 (0,3)입니다.

하지만, n이 3이기 때문에, (0,3)의 위치는 없습니다. 이 때, 행을 1 늘리고 열을 다시 0으로 만들어줍니다.

그럼 이제 다음 위치는 (1,0)이 됩니다.

그럼 이대로 쭉 벽을 안세워서 마지막 위치인(2,2)까지 갔다고 해봅시다.

               

해당 위치에서도 벽을 만들지 않았고, 다음 위치는 (3,0) 입니다.

하지만, (3,0)은 없는 위치죠. 아무 일도 하지 않고 종료합니다.

즉, 다음 벽돌을 만들 때에는,

기본적으로 현재 행과 열을 기준으로, 열을 1씩 늘립니다.

열이 n과 같아지면, 행을 1 늘려주고 열을 0으로 만듭니다. 

이 때, 행이 n과 같아지면 아무일을 하지 않고 종료하면 2차원 공간에 대한 조합을 시행할 수 있습니다.

2번은 대표적인 bfs방식을 이용해서 구현하시면 됩니다.

바이러스의 위치들을 큐에 넣고, 2차원 visit 배열을 만듭니다.

해당 바이러스의 위치에서 위, 아래, 왼쪽, 오른쪽이 벽이 아니면서 바이러스가 없을 경우에 해당 위치도 큐에 넣고 바이러스가 있도록 만듭니다.

그럼 이제 위처럼 됩니다.

코드

#pragma once
#include<iostream>
#include<cstring>
 
using namespace std;
 
int n, m, map[8][8];
int wall;
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
 
int spread() {
    bool visit[8][8] = {};
    int que[100][2], s, e;
    int virus = 0;
 
    s = e = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 2) {
                que[e][0]= i;
                que[e++][1] = j;
 
                visit[i][j] = true;
            }
        }
    }
 
    
    while (s != e) {
        int now[2] = { que[s][0], que[s++][1] };
        virus++;
 
        for (int d = 0; d < 4; d++) {
            int next[2] = { now[0] + dr[d], now[1] + dc[d] };
            
            if (next[0] < 0 || next[1] < 0 || next[0] >= n || next[1] >= m) continue;
            if (visit[next[0]][next[1]]) continue;
            if (map[next[0]][next[1]]) continue;
            visit[next[0]][next[1]] = true;
            
            que[e][0] = next[0];
            que[e++][1] = next[1];
        }
    }
 
    return n*m - e - wall - 3;
}
 
int MAX(int i1, int i2) {
    return i1 < i2 ? i2 : i1;
}
 
int choose(int cnt, int r, int c) {
    if (cnt == 3) {
        return spread();
    }
 
    if (r == n) return 0;
    
    int next[2] = { r, c + 1 };
 
    if (c + 1 == m) {
        next[0] = r + 1;
        next[1] = 0;
    }
 
    int res = choose(cnt, next[0], next[1]);
 
    if (map[r][c] == 0) {
        map[r][c] = 1;
 
        res = MAX(res, choose(cnt + 1, next[0], next[1]));
 
        map[r][c] = 0;
    }
    
    return res;
}
 
int main() {
    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] == 1) wall++;
        }
    }
 
    cout << choose(0, 0, 0);
 
    return 0;
}
 

시간 복잡도

시간복잡도는 벽을 세우기 위해, 그리고 바이러스가 확산하기 위해의 연산이 필요하므로,

총 시간 복잡도는 입니다.