[백준알고리즘] 14502번 연구소

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

문제를 복붙해서 올렸었는데 그냥 다시 캡처로 올려야지^^* 폰으로 볼 때  다 잘린다 ㅠㅠ

ㅎㅎㅎㅎ 이런 ㅎㅎㅎㅎㅎㅎㅎ

아 지금까지.. 나는 비주얼 콘솔창에서 깜빡이는 게 제출했을 때 제한시간 1초랑 같은 것인 줄 알았다.. 

그래서 문제의 예제 3번 돌릴 때 계속 오랜시간이 걸리길래 어떻게 하면 시간을 줄일 수 있나 한참 고민했는데... 결국에는 콘솔창에서 돌리는 시간이랑 문제의 시간제한 조건이랑은 다른 것이어서.... 그냥 제출해도 되는 것이었다 허무...

line 58 :: 나는 큐의 상태를 복원하기 위해 같은 큐를 하나를 더 만들어 덮어씌워주는 방식으로 하였다!

line 49 :: 그리고 map 배열은 바꿨다가 다시 되돌리기 힘들 것 같아 map 자체는 0에서 2로 변경하지 않고 지역변수인 visited 배열로만 제어하였다.

struct node 형식의 vector 쓴 거는.. 조금이라도 시간을 줄여보려고 애썼던 흔적... 결과적으로 쓸모는 크게 없었다 ㅠ

벽을 놓을 수 있는 공간(map == 0 인 공간)만 저장하여 vector에 넣어주어 map 전체로 반복문을 돌리는 것보다는 시간을 빠르게 하려고 했었다..

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
 
struct node
{
    int x;
    int y;
};
 
int N, M;
int safe_zone = -3;
int map[65][65];
queue<pair<int, int>> q;
queue<pair<int, int>> cp_q;
 
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
 
vector<node> v;
 
int max_safe_zone = 0;
 
void bfs()
{
    bool visited[65][65] = { false };
    int count = 0;
 
    while (!q.empty())
    {
        int sz = q.size();
        while (sz--)
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                int mx = x + dx[i];
                int my = y + dy[i];
 
                if (mx >= 0 && mx < N && my >= 0 && my < M)
                {
                    if (map[mx][my] == 0 && !visited[mx][my])
                    {
                        q.push(make_pair(mx, my));
                        visited[mx][my] = true;
                        count++;
                    }
                }
            }
        }
    }
    int local_safe_zone = safe_zone - count;
    if (max_safe_zone < local_safe_zone) max_safe_zone = local_safe_zone;
    q = cp_q;
 
    return;
}
 
void build_wall(int ord, int i, int j, int _count)
{
    map[i][j] = 1;
 
    // 벽 3개를 세웠다. 바이러스 확산
    if (_count == 3)
    {
        bfs();
        return;
    }
 
    for (int i = ord+1; i < v.size(); i++)
    {
        if (map[v[i].x][v[i].y] == 0)
        {
            build_wall(i,v[i].x,v[i].y,_count+1);
            map[v[i].x][v[i].y] = 0;
        }
    }
    return;
}
int main(void)
{
    int count = 0;
    cin >> N >> M;
 
    node nd;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 0)
            {
                safe_zone++;
                nd.x = i;
                nd.y = j;
                v.push_back(nd);
            }
            if (map[i][j] == 2) {
                q.push(make_pair(i, j));
                cp_q.push(make_pair(i, j));
            }
        }
    }
    for (int i = 0; i < v.size()-2; i++)
    {
        build_wall(i,v[i].x, v[i].y, count + 1);
        map[v[i].x][v[i].y] = 0;
    }
 
    cout << max_safe_zone;
 
    return 0;
}