[ 백준 17142 ] 연구소3 (C++)

[문제보기]

 

[해결과정]

 1. input

  -> n, m, arr 맵

  --> 빈칸(0)의 갯수 카운트 하기 : if(arr 맵 == 0) k++

 

 2. DFS 완전탐색

  -> 맵을 순회하며, 비활성바이러스를 발견하면, -1로 변경후 다음 DFS 수행

 

 3. DFS 수행 중 Count 개수가 m과 같다면, 기능 실행

  -> check 함수 -1로 초기화

  -> DFS를 통해 활성바이러스로 바꾼 좌표를 큐에 삽입 (맵==-1)

  -> BFS() 수행

 

 4. inf (0을 1로 바꾼 개수) , times (걸린 시간) 변수 선언

 5. while(!q.empty()) 수행

  -> 4방향 탐색하며, check == -1 && arr!=1 인 곳 방문

  -> 만약 arr=0 이면 방문할 때 시간으로 times 갱신, inf++ 수행

 

 6. ans와 times를 비교하여 최소값으로 갱신

 7. ans가 초기 값 987987987 이라면 -1 출력, 아니라면 ans 값 출력

 

[소스코드]

/*
    BOJ 17142 - 연구소3
    Created by haejun on 2020/03/18
*/
#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;
 
const int MAX = 52;
int arr[MAX][MAX];
int temp[MAX][MAX];
int check[MAX][MAX];
 
int n, m;
 
int ans = 987987987;
int k = 0;
 
//구조체
struct coor {
    int y;
    int x;
};
queue <coor> q;
 
//inside check
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < n;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void BFS() {
    int inf = 0, times = 0;
    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 = y + dy[i];
            nx = x + dx[i];
            if (inside(ny, nx) && check[ny][nx] == -1 && arr[ny][nx] != 1) {
                q.push({ ny,nx });
                check[ny][nx] = check[y][x] + 1;
                if (arr[ny][nx] == 0) {
                    times = check[ny][nx];
                    inf++;
                }
            }
 
        }
    }
    if (inf == k && ans > times) ans = times;
}
 
 
void pickDFS(int count, int sy, int sx) {
    if (count == m) {
        //실행할 곳
        memset(check, -1, sizeof(check));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == -1) {
                    q.push({ i,j });
                    check[i][j] = 0;
                }
            }
        }
        BFS();
 
        return;
    }
 
    for (int y = sy; y < n; y++) {
        for (int x = sx; x < n; x++) {
            if (arr[y][x] == 2) {
                arr[y][x] = -1;
                pickDFS(count + 1, y, x);
                arr[y][x] = 2;
            }
        }
        sx = 0;
    }
}
 
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 0) k++;
        }
    }
 
    pickDFS(0, 0, 0);
 
    if (ans == 987987987) {
        cout << "-1" << endl;
    }
    else {
        cout << ans << endl;
    }
 
    return 0;
}

 

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

 이 문제에서 주의해야 할 부분은, 비활성바이러스 부분을 활성바이러스로 바꾸는 과정에 시간을 어떻게 처리할 것인가가 문제였다.

 

 함정은, 마지막 비활성바이러스 1개 남았을때, 이것을 활성으로 바꿨을 때 시간을 +하냐, 마냐 문제였다.

 

 이 부분을 해결하기 위해서, 초기 0값인 부분이 바꼈을 때 만 시간을 바꾸는 방법을 사용했다.

 

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

 삼성 역량 테스트