연구소 3 #

TimeLimit	MemoryLimit	Condition	TAG
0.25s	512MB	(4 ≤ N ≤ 50, 1 ≤ M ≤ 10)	BFS

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2
M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.
* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *
시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.
0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *
연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

정말 충격이였다.. 처음에 짠 bfs 코드를 문제를 또 잘못 읽고서 풀어서 다른 문제를 풀어버려쏙 다시 풀어서 제출하니 시간초과 어머나…

그래서 다시 보니 아 이걸 중복 검사가 있어서 다시 제출 그러다 다시 시간 초과…

아 그 이후에 dfs를 다시 중복 없이 검사 및 빨리 끝나도록 설계해서 다시 제출 그러나 또 시간초과

알고보니까 bfs 코드를 조금 다시 보니 다익스트라 마냥 짜놔서 이거 방문 이후에 검사하는 방식이여서 최악의 경우 한 노드당 방문 수가 4가 되면서 O(N^4)을 찍어ㅑ버렸다.

미치겠다.. 이걸 왜 이렇게 짠 걸까.. 총 문제 풀이 시간은 길지 않았으나.. 이렇게 틀리고, 멘탈이 흔들리니 아직도 많이 방심하는 성격이 있는 것 같다. 항상 긴장하고 코드 한줄한줄마다 시간 복잡도 생각하면서 작성해야겠다.

정답 코드

부끄럽네요...

다음부터는 좋은 코드로 돌아오겠습니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;

const int INF = 1e9;
const int MAX_N = 51;
int n, m;
int board[MAX_N][MAX_N], use[MAX_N][MAX_N];
pair<int, int> vir[10];
int virCnt = 0;
int emptySpace = 0;

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

void init(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(board[i][j] == 1) use[i][j] = -1;
            else use[i][j] = INF;
        }
    }
}

int solution(vector<pair<int, int>>& current){
    init();
    queue<pair<int, pair<int, int>>> q;
    int filled = 0;
    
    for(auto& p : current) {
        q.push({0, p});
        use[p.first][p.second] = 0;
    }
    
    int maxTime = 0;
    while(!q.empty() && filled < emptySpace){
        auto [time, pos] = q.front();
        auto [y, x] = pos;
        q.pop();
        
        if(board[y][x] != 2) {
            maxTime = time;
            filled++;
        }
        
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny >= n || nx < 0 || nx >= n || use[ny][nx] != INF) continue;
            use[ny][nx] = time + 1;
            q.push({time + 1, {ny, nx}});
        }
    }
    
    return filled == emptySpace ? maxTime : INF;
}

int search(int idx, vector<pair<int, int>>& current){
    if(current.size() == m) return solution(current);
    if(idx >= virCnt || virCnt - idx < m - current.size()) return INF;
    
    int result = INF;
    
    current.push_back(vir[idx]);
    result = min(result, search(idx + 1, current));
    current.pop_back();
    
    result = min(result, search(idx + 1, current));
    
    return result;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> board[i][j];
            if(board[i][j] == 2) vir[virCnt++] = {i, j};
            else if(board[i][j] == 0) emptySpace++;
        }
    }
    
    vector<pair<int, int>> vec;
    int result = search(0, vec);
    
    cout << (result == INF ? -1 : result);
    return 0;
}

연구소 3#

연구소 3 #