연구소_14502

문제 출처 : 연구소_14502

파라미터 정리

NxM 직사각형, N:row, M:col (3~8)
0 : 빈칸 (3~)
1 : 벽
2 : 바이러스 (벽을 만날때까지 상하좌우로 퍼짐) (2~10)
추가로 3개의 벽을 세움
원하는 것 = 벽 3개를 세워 바이러스 확산을 최소화하기
출력 : 안전 영역(0)의 개수

간단한 과정

input_1 N,M 입력 받기
input_2 초기 맵 정보 Map[8][8]에 입력값 받기
새로운 벽 3가지를 세우는 경우를 구하기
각 방법에서 바이러스 전파시키기 (벽을 만나거나 범위를 벗어날 때까지 2로 만들기)
이때 안전 지역 개수 세기 (전체 중 0으로 된 값 세기)
모든 경우의 수에 대해 안전 지역 개수 최댓값(res) 구하기
output res 출력하기

코드

재귀호출함수를 이용한 DFS로 풀었을 때 (40ms)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

struct location{
    int r,c;
};
int N,M;
int Map[8][8];
vector<location> l_virus;
int Dr[4] = {1,0,-1,0};
int Dc[4] = {0,1,0,-1};

void move_virus(location input){
    int nr = input.r, nc = input.c;
    if(nr < 0 || nc < 0 || nr > N-1 || nc > M-1) return;
    if(Map[nr][nc] == 1 || Map[nr][nc] == 9) return;
    
    Map[nr][nc] = 9;
    
    for(int i = 0; i < 4; i++){
        location temp = {nr+Dr[i], nc+Dc[i]};
        move_virus(temp);
    }
    return;
}

int solve(int pos, int cnt){
    if(cnt < 3 && pos >= N*M) return 0;
    if(cnt == 3){
        //바이러스 최대한 전파
        for(auto iter = l_virus.begin(); iter != l_virus.end(); iter++)
            move_virus(*iter);
        //필드에서 0의 개수 구하기
         int num = 0;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                if(Map[i][j] == 0)  num++;
        return num;
    }
    
    int res = 0;
    int row = pos/M, col = pos%M;
    int copyMap[8][8];
    if(Map[row][col] == 0){
        memcpy(copyMap, Map, sizeof(Map));
        Map[row][col] = 1;
        res = max(res, solve(pos+1,cnt+1));
        memcpy(Map, copyMap, sizeof(Map));
    }
    res = max(res, solve(pos+1,cnt));
    
    return res;
}

int main()
{
    
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> Map[i][j];
            if(Map[i][j] == 2)
                l_virus.push_back({i,j});
        }
    }
    cout << solve(0,0) << endl;

    return 0;
}

queue를 이용한 BFS로 풀었을 때(956ms)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

struct loc{
  int r,c;  
};
int N,M;
int Map[8][8];
vector<loc> virus;
int Dr[4] = {1,0,-1,0};
int Dc[4] = {0,1,0,-1};

int checkblank(){//0의 개수를 세는 함수
    int res = 0;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            if(Map[i][j]==0) res++;
    return res;
}

void diffuse(){
    for(int i = 0; i < virus.size(); i++){
        int r = virus[i].r, c = virus[i].c;
        queue<loc> myqueue;
        myqueue.push({r,c});
        do{
            loc curr = myqueue.front();
            myqueue.pop();
            int nr = curr.r, nc = curr.c;
            Map[nr][nc] = 9;
            for(int j = 0; j < 4; j++){
                nr = curr.r+Dr[j];
                nc = curr.c+Dc[j];
                if(nr<0||nc<0||nr>N-1||nc>M-1) continue;
                if(Map[nr][nc]!=0) continue;
                myqueue.push({nr,nc});
            }
        }while(!myqueue.empty());
    }
    return;
}

int solve(int cnt,int pos){
    if(cnt<3 && pos>=N*M) return 0;
    if(cnt==3){
        diffuse();
        return checkblank();
    }
    int res = 0;
    int row = pos/M, col = pos%M;
    int copyMap[8][8];
    if(Map[row][col]==0){
        memcpy(copyMap,Map,sizeof(Map));
        //현재 칸을 선택했을 때
        Map[row][col] = 1;
        res = max(res,solve(cnt+1,pos+1));
        memcpy(Map,copyMap,sizeof(Map));
    }
    //현재 칸을 선택하지 않았을 때
    res = max(res,solve(cnt,pos+1));
    
    return res;
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> Map[i][j];
            if(Map[i][j]==2) virus.push_back({i,j});
        }
    }
    cout << solve(0,0) << endl;

    return 0;
}

시행착오

백업_0529_am01:20
완성했는데 값이 똑바로 안나옴
예제 1 결과로 0 나옴 예제 23도 이상하게 나옴
->문제점: 모든 경우의수를 국하지 못하고 처음 3개 선택후 끝나버림
->벽을 안세우고 스킵하는 부분을 else 부분에 넣어서 3개만 선택하고 끝난 던 것
->pos가 계속 증가하는 거 고치고, 회귀할 때 그 전 조건과 같게 만들어줌