[BOJ] 연구소

[문제]

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

14502번: 연구소

[풀이]

14502

맞았습니다!!

1988 KB

36 ms

C++14 / 수정

2189 B

1분 전

 

1) 너비우선탐색 문제

 

2) 새로운 벽을 3개 세워야 한다.  여기서 조합을 생각했음

 

3) dfs로 벽 3개의 조합을 만들고, spreadVirus에서 큐를 이용하여 완전 탐색한다. 

 

4) 맵이 변형되기 때문에 맵을 복사 후에 바이러스를 퍼트리고 그 때의 안전 공간의 최대 값을 구해야 한다. 

---

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
//풀이 : 25분 
 
int n, m, map[9][9], max_safe = 0;
bool visited[9][9];
typedef pair<int, int> pp;
 
vector<pp> virus;
 
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
 
void printMap()
{
    cout << '\n';
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}
void spreadVirus()
{
    queue<pp> q;
 
    memset(visited, false, sizeof(visited));
 
    for (int i = 0; i < virus.size(); i++)
    {
        q.push(virus[i]);
        visited[virus[i].first][virus[i].second];
    }
 
    while (!q.empty())
    {
        int size = q.size();
 
        while (size--)
        {
 
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny])
                    continue;
 
                if (map[nx][ny] == 1)
                    continue;
                else if (map[nx][ny] == 2)
                    continue;
                else
                {
                    //3으로 표시 (바이러스가 퍼진 영역 )
                    map[nx][ny] = 3;
                    visited[nx][ny] = true;
                    q.push(pp(nx, ny));
                }
            }
        }
    }
 
    int safe = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] == 0) safe++;
        }
    }
 
    if (max_safe < safe) max_safe = safe;
 
   
}
void dfs(int cnt)
{
    if (cnt == 3)
    {
        int c_map[9][9];
        memcpy(c_map, map, sizeof(map));
 
        //3개의 벽을 다 세움
       
        spreadVirus();
        
        memcpy(map, c_map, sizeof(c_map)); //맵 원상 복구
 
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!map[i][j])
            {
                map[i][j] = 1;
                dfs(cnt + 1);
                map[i][j] = 0;
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            // c_map[i][j] = map[i][j];
 
            if (map[i][j] == 2)
            {
                virus.push_back(pp(i, j));
            }
 
        }
    }
    //input
 
    dfs(0); //벽 세우기
 
    cout << max_safe << '\n';
    return 0;
}