[ 백준 14502 ] 연구소 (C++)

[문제보기]

 

[해결과정]

 1. 큐(bv) 생성 후 바이러스 좌표를 넣기.

 2. 큐(q) 생성

 

 3. dfs로 벽 3개 세우기 (조합 사용)

  - 세운 벽은 큐(q)에 넣기

 

 4. 기저조건에 맞는 상태면 바이러스 활성화 해서 모두 퍼뜨리기 

 5. 가장 많은 빈공간이라면 답 갱신

 

 6. 동작 후 맵은 원복, 방문 체크는 초기화

 

 

[소스코드]

#include<iostream>
#include<math.h>
#include<queue>
#include<vector>
#include<memory.h>
using namespace std;
const int MAX = 9;
 
int one[MAX][MAX];
int arr[MAX][MAX];
bool visit[MAX][MAX];
bool check[MAX][MAX];
int n, m;
 
// 정답
int ans = 0;
 
// 좌표 구조체
struct coor {
    int y;
    int x;
};
vector <coor> v;
 
// 초기 바이러스 위치 저장할 공간
vector<coor> bv;
 
// bfs할 큐
queue <coor> q;
 
// inside check
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < m;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
 
void bfs() {
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = dy[i] + y;
            nx = dx[i] + x;
            if (inside(ny, nx) && visit[ny][nx] == 0 && arr[ny][nx] == 0) {
                visit[ny][nx] = 1;
                arr[ny][nx] = 2;
                q.push({ ny,nx });
            }
        }
    }
}
 
//조합 테스트
void dfs(int cnt, int a, int b) {
    if (cnt == 3) {
        //기저조건
        memcpy(arr, one, sizeof(one));
 
        for (int i = 0; i < 3; i++) {
            arr[v[i].y][v[i].x] = 1;
        }
 
        int cnt = 0;
 
        for (int i = 0; i < bv.size(); i++) q.push({ bv[i].y, bv[i].x });
 
        bfs();
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 0) cnt++;
            }
        }
        memset(visit, 0, sizeof(visit));
        
 
        for (int i = 0; i < 3; i++) {
            arr[v[i].y][v[i].x] = 0;
        }
 
        if (cnt > ans) ans = cnt;
 
 
        return;
    }
 
    for (int i = a; i < n; i++) {
        for (int j = b; j < m; j++) {
            if (check[i][j] == 0 && one[i][j]==0) {
                check[i][j] = 1;
                v.push_back({ i,j });
                dfs(cnt + 1, a, b);
                v.pop_back();
                check[i][j] = 0;
            }
        }
        b = 0;
    }
 
}
 
 
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 >> one[i][j];
            if (one[i][j] == 2) bv.push_back({ i,j });
        }
    }
 
    dfs(0, 0, 0);
 
 
    cout << ans << "\n";
 
    return 0;
}

 

 

[해결 과정 중 실수한 부분 / 잡담]

 dfs와 bfs가 모두 사용되는 전형적인 삼성의 기본 문제였다.

 

[관련 문제 혹은 비슷한 문제]

 삼성 기출