백준 14502 연구소 c++ (dfs bfs)

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <memory.h>

using namespace std;

typedef struct point {
    int x=0;
    int y=0;
}points;

queue<point> que;
points p;

int laboratory[11][11];
int copy_laboratory[11][11];
int n=0;
int m=0;
int xmove[4] = {1,0,-1,0};
int ymove[4] = {0,1,0,-1};
int cnt=0;
int result = 0;

 

///x와 y가 경계를 넘어가지는지 체크
bool inside(int x, int y) {  
    if(0<x && x<=m && 0<y && y<=n) {
        return true;
    }
    return false;
}


void bfs() { 
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(laboratory[i][j] == 2) {
                p.x = j;
                p.y = i;
                que.push(p);
            }
        }
    }
    memcpy(copy_laboratory, laboratory, sizeof(laboratory));

    //laboratory배열 복사

    while(!que.empty()) {
        int xpos = que.front().x;
        int ypos = que.front().y;
        que.pop();
        for(int i=0; i<4; i++) {
            int map_x = xpos+xmove[i];
            int map_y = ypos+ymove[i];
            if(inside(map_x, map_y) == true) {
                if(laboratory[map_y][map_x] == 0) {
                    laboratory[map_y][map_x] = 2;
                    p.x = map_x;
                    p.y = map_y;
                    que.push(p);
                }
            }
        }
       //바이러스 옮기기
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(laboratory[i][j] == 0) {
                cnt+=1;
            }
        }
    }
/*
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            printf("%d ", laboratory[i][j]);
        }
        printf("\n");
    }

    printf("!!!!!!!!!!!!!!!!!!!!!!!!!! \n");
*/
    memcpy(laboratory, copy_laboratory, sizeof(copy_laboratory));

     //다시 초기에 복사한 copy_laboratory로 laboratory배열 복사(원래의 배열로 다시 바꾸어줘야하므로)

    //왜냐하면 배열이 bfs로 인해 2로바뀐것들이 있음
    /*
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            printf("%d ", laboratory[i][j]);
        }
        printf("\n");
    }

    printf("~~~~~~~~~~~~~~~~~~`` \n");
    */
    result = max(result, cnt);
    //printf("cnt : %d \n", result);
    cnt = 0;
   //cnt초기화
}

void dfs(int cnt) { //make wall
    if(cnt==3) {
        bfs();
        return;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(laboratory[i][j] == 0) {
                laboratory[i][j] = 1;
                dfs(cnt+1);
                laboratory[i][j] = 0;
            }
        }
    }
}
//벽옮기기
int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%d", &laboratory[i][j]);
        }
    }
/*
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            printf("%d", copy_laboratory[i][j]);
        }
        printf("\n");
    }
*/


    dfs(0);

    printf("%d", result);



    return 0;
}

 

dfs로 벽을옮겨주고 bfs로 바이러스를 옮겨주는 문제이다