백준 17141. 연구소2

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

17141번: 연구소 2

 

재귀를 이용한 dfs로 m개의 바이러스를 살포할 위치를 찾고 bfs 탐색을 진행했는데 시간초과가 났다.

일단 내일 다시 풀어보는걸로..

 

시간초과 난 코드:

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int n,m;
int ans = 999;
int map_org[51][51];

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
bool mark[51][51];

// mark 초기화
void InitMark()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            //map[i][j] = map_org[i][j]; 맵복사 필요없음
            mark[i][j] = false; // mark도 초기화
        }
    }
}


// 바이러스 살포안된곳 있는지 판별
bool AllVisited()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            // 벽이면 continue
            if(map_org[i][j] == 1) continue;
            // 방문안한곳 있으면 false 리턴
            if(!mark[i][j]) return false;
        }
    }
    return true;
}

void bfs()
{
    queue<pair<pair<int,int>,int>> q;
    // 바이러스 살포하기로 정한 위치를 큐에 푸쉬한다
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(map_org[i][j] == 5)
            {
                q.push({{i,j},0});
                mark[i][j] = true;
            }
        }
    }

    int time;
    while(!q.empty())
    {
        int _r = q.front().first.first;
        int _c = q.front().first.second;
        time = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nr = _r + dr[i];
            int nc = _c + dc[i];

            // 범위 벗어남
            if(nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            // 벽이거나 이미 방문했다면 continue
            if(map_org[nr][nc] == 1 || mark[nr][nc]) continue;

            mark[nr][nc] = true;
            q.push({{nr,nc}, time+1});
        }
    }


    // 바이러스가 모든곳에 살포되었다면 최소시간 갱신
    if(AllVisited())
    {
        ans = min(ans, time);
    }
}



// m개의 바이러스를 놓을곳을 찾는다
void dfs(int virusNum)
{
    // 놓을수 있는 모든 바이러스를 놓았다면
    if(virusNum == m)
    {
        InitMark();
        bfs();

        return;
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            // 바이러스를 놓을수 있는곳이면
            if(map_org[i][j] == 2)
            {
                map_org[i][j] = 5; // virus 표시
                dfs(virusNum+1);
                map_org[i][j] = 2;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> map_org[i][j];
        }
    }

    dfs(0);

    // ans가 최초값에서 변하지 않았다면 어떻게 놓아도 모든 빈칸에 바이러스를 살포할수 없다는 뜻이다
    if(ans == 999)
        ans = -1;

    cout << ans;

}

 

 

---

2021.07.30

 

시간초과 나지 않도록 다시 풀어봤다.

이전 코드에서는 바이러스를 살포할때마다 새로운 map 2차원 배열을 만들어서 시간을 일일히 기록했는데

생각해보니 그렇게 하지 않고 그냥 bool visited[][] 배열에 방문여부만 표시하고 큐의 깊이로 시간을 따지기만 하면 된다.

이렇게 하면 이전에 일일히 기록하고 초기화하고를 반복하는 것 보다 훨씬 빠르게 수행할수 있다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int n,m;
int ans = 999999999;
int map[51][51];
bool visited[51][51];
bool mark[11];
vector<pair<int,int>> virusPutLoc;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

// m개 지점에 바이러스를 살포했을때, 벽을 제외한 모든곳이 감염되었는지 판별
bool IsAllInfected()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(map[i][j] == 1) continue; // 벽은 제외
            if(!visited[i][j]) return false;
        }
    }
    return true;
}


void InitVisited()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            visited[i][j] = false;
        }
    }
}

void bfs()
{
    // {r,c}, {time}
    queue<pair<pair<int,int>,int>> q;
    // 현재 바이러스를 살포하기로한 m개의 좌표를 큐에 푸쉬한다
    for(int i = 0; i < virusPutLoc.size(); i++)
    {
        if(mark[i])
        {
            q.push({{virusPutLoc[i]},0});
            visited[virusPutLoc[i].first][virusPutLoc[i].second] = true;
        }
    }

    int time = 0;
    while(!q.empty())
    {
        int _r = q.front().first.first;
        int _c = q.front().first.second;
        time = q.front().second;
        //if(time > maxTime) maxTime = time;
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nr = _r + dr[i];
            int nc = _c + dc[i];

            if(nr < 0 || nr >= n || nc < 0 || nc >= n) continue;

            if(!visited[nr][nc] && map[nr][nc] != 1)
            {
                visited[nr][nc] = true;
                q.push({{nr,nc}, time+1});
            }
        }
    }

    // 벽을 제외한 모든곳이 감염되었다면 최소시간 갱신
    if(IsAllInfected())
        ans = min(ans, time);

    InitVisited(); // visited 배열 초기화
}

// virusPutLoc.size()개 중에서 m개의 바이러스 살포 위치를 정한다 (조합)
void dfs(int index, int numOfVirus)
{
    // m개의 위치를 정했다
    if(numOfVirus == m)
    {
        // 바이러스 살포
        bfs();

        return;
    }

    for(int i = index; i < virusPutLoc.size(); i++)
    {
        if(mark[i]) continue;
        mark[i] = true;
        dfs(i, numOfVirus+1);
        mark[i] = false;
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> map[i][j];
            // virus를 놓을수 있는 칸의 좌표를 벡터에 저장해놓는다
            if(map[i][j] == 2)
                virusPutLoc.push_back({i,j});
        }
    }

    dfs(0,0);

    // ans가 초기값에서 변하지 않았다면 바이러스를 어떻게 놓아도 모든 빈칸에 바이러스를 퍼트릴수 없다는 것
    if(ans == 999999999)
        cout << -1 << '\n';
    else
        cout << ans << '\n';

}