[C++] 백준 #14502 연구소

문제

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

14502번: 연구소

 

생각해 본 것

벽을 딱 3개 세워야 하니까 처음에는 보드의 (x, y)를 mx+y 수식을 통해 일차원 배열로 만들고,

그 중 3개를 비트마스크를 통해 고르고,

고른 것을 바탕으로 바이러스 확산과 안전구역 계산을 하려고했다.

그런데 비트마스크가 너무 오랜만이라서 생각은 했으나 구현이 어려웠다..

(8*8 배열이고 1자로 펼치면 8*8+8=72개의 비트가 필요한게 아닌가? 생각이 들면서 점점 미궁에 빠졌음..) 

 

그래서 다른 사람의 코드를 참조해서 해결했다.

1. 처음 배열을 입력받을 때 pair<int, int> 형인 space 벡터에 (x, y)를 기록한다.

2. 벽을 세운다 

1. bool 자료형인 visited배열을 8*8 크기로 선언함 (space 벡터 중 3개를 선택하기 위함)
2. visited 배열에서 선택한 칸이 3개가 되면 시뮬레이션을 시작함 : 입력받은 보드를 복사해서 하나 더 만들고, 거기에 visited 배열을 바탕으로 벽을 세운다.

3. 바이러스 확산과 안전구역 계산

1.  queue를 사용해 복사한 보드에서 2인 곳의 위치(x, y)를 queue에 넣고
2.  queue에 아무것도 없을 때까지 상하좌우가 0이면 거기를 2로 만들고 queue에 해당 좌표를 넣는다.
3.  확산된 배열을 바탕으로 안전구역 계산을 한다.

 

//
// Created by ღ 𝚂𝚑𝚒𝚗𝚎 𝚈𝚎𝚘𝚗 ღ on 2022/07/22.
//

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
int a[9][9]; //입력받는 배열
int tmp[9][9]; //계산하는 배열
int dx[4] ={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0};
bool visited[9*9];
int ans=0;
vector<pair<int, int>> space;

void copy(int tmp[9][9], int a[9][9]){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            tmp[i][j] = a[i][j];
        }
    }
}

void bfs() {
    queue<pair<int, int>> q;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(tmp[i][j] == 2)
                q.push({i, j});
        }
    }

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int k=0; k<4; k++){
            int nx = x+dx[k];
            int ny=y+dy[k];
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(tmp[nx][ny] == 0){
                tmp[nx][ny]=2;
                q.push({nx, ny});
            }
        }
    }
    int cnt =0;
    for(int i=0; i<n; i++){
        for(int j=0;j<m; j++){
            if(tmp[i][j]==0)
                cnt++;
        }
    }
    if(ans<cnt) ans=cnt;
}

void wall(int cur, int idx) {
    if(cur==3) {
        copy(tmp, a);
        //int cnt = 0;
        for(int i=0; i<space.size(); i++){
            //if(cnt==3) break;
            if(visited[i]){
                int x=space[i].first;
                int y=space[i].second;
                tmp[x][y] = 1;
                //cnt++;
            }
        }
        bfs();
        return;
    }
    for(int i=idx; i<space.size(); i++){
        if(visited[i]) continue;
        visited[i] = true;
        wall(cur+1, i+1);
        visited[i] = false;
    }
}

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<m; j++){
            cin>>a[i][j];
            if(a[i][j]==0){
                space.push_back({i, j});
            }
        }
    }
    wall(0, 0);
    cout<<ans<<"\n";


}

wall() 함수에서 주석처리한 부분은 참고 코드에 있던 부분인데,

생각해보니 없어도 될 것 같아서 주석처리해봤다.

제출결과, 없어도 되는 코드였다..!

 

백준 14502 제출결과