[백준]연구소3

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

17142번: 연구소 3

너무 억울하다 .... 하루종일 이문제에 매달렸는데 로직자체에는 문제가 없었는데 그냥 answer를 너무 작은값으로

해줘서 오류가 났던거 였다.... answer=1e9로 해주니까 오류가 안났다........... 하 ㅆㅂ.

참고로 1e9는 1*10^9 이다.

먼저, 문제를 읽고 나서 든 생각은 dfs,bfs를 같이 사용해야겠다고 생각했다.

문제의 핵심은 아래와 같다

1.주어진 바이러스들중 M개를 어떻게 선택할 것인지 --> (조합)

-->for문의 시작점을 어떻게 하느냐에 따라서 순열, 조합이 될 수 있다.

2.선택된 바이러스들로 부터 그냥 bfs를 실행해주면 된다.

3.가장 중요한건은 비활성화 바이러스이다. 처음에는 있으나 없으나 라고 생각을 했지만 비활성화 바이러스가 

중간에 있느냐, 마지막벽에 있느냐에 따라 시간이 달라지게 된다. 이걸 구현하는게 좀 까다로웠다.

구현 방법은 더이상 전염될 것이 있느냐 없느냐를 구현하는 것이고, 4방향을 탐색할수도 있고 0의 개수를 셀수도 있다.

 

<초기 코드(좀 번잡함)>

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
struct Birus {
    int r;
    int c;
    bool Alive;
    Birus() {};
    Birus(int r, int c, bool Alive) :r(r), c(c), Alive(Alive) {};
};
 
int N, M, cnt=0,answer = 1000,1e-9(정답), 1000보다 커지는 경우가 생김 ㅋㅋ;
int b_cnt=0;
int map[51][51];
int isV[51][51];
int dr[] = {0,0,1,-1}, dc[] = {1,-1,0,0};
queue<pair<int, int> > q1;
vector<pair<int, int> >start_v;
vector<Birus> birus;
 
void Show() {
    printf("=================================================\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) { if (isV[i][j] == 0) printf("- "); else printf("%d ", isV[i][j] - 1); }
        printf("\n");
    }
}
 
 
int bfs() {
    int a,b=b_cnt;
    memset(isV, 0, sizeof(isV));
    for (int i = 0; i < M; i++) {
        q1.push(make_pair(start_v[i].first,start_v[i].second));
        isV[start_v[i].first][start_v[i].second]=1; //방문
    }
 
    while (!q1.empty()) {
        int nr = q1.front().first, nc = q1.front().second;
        q1.pop();
        a = isV[nr][nc]-1;
        
        for (int i = 0; i < 4; i++) {
            int nnr = nr + dr[i], nnc = nc + dc[i];
            if (nnr < 0 || nnc < 0 || nnr >= N || nnc >= N) continue;
            if (isV[nnr][nnc] == 0 && map[nnr][nnc] == 0) {
                q1.push(make_pair(nnr, nnc));
                isV[nnr][nnc] = isV[nr][nc] + 1;
                b--;
            }
            else if (isV[nnr][nnc] == 0 && map[nnr][nnc] == 2) { //비활성화바이러스
                if (b > 0) { //0이 남아있다면
                    q1.push(make_pair(nnr, nnc));
                    isV[nnr][nnc] = isV[nr][nc] + 1;
                }
                else {
                    isV[nnr][nnc] = isV[nr][nc];
                }
            }
        }
    }
    //printf("%d %d\n",a, b);
    if (b > 0) return 100;
    return a;
}
 
void dfs(int start,int len) {
    if (len == M) { 
        //bfs gogo    
        int b = bfs();
        //Show();
        if (b != 100) {
            if (answer >= b) answer = b;
        }
        if (b == 0) { answer = 500;} ///////이부분이 제일 번잡한거 같다.(스킬부족)
        return; 
    }
 
    for (int i = start; i < birus.size(); i++) {
        if (birus[i].Alive == false) {
            birus[i].Alive = true;
            start_v.push_back(make_pair(birus[i].r,birus[i].c)); //바이러스 선택
            dfs(i,len + 1); //뒤로만 진행하기위해서 (순열과 조합의 차이)
            birus[i].Alive = false;
            start_v.pop_back();
        }
    }
}
 
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) { 
        for (int j = 0; j < N; j++) { 
            cin >> map[i][j];
            if (map[i][j] == 0) b_cnt++; //감염되어야 하는 '0'의 수
            if (map[i][j] == 2) { birus.push_back(Birus(i, j, false)); } //바이러스 정보 대입
        }
    }
 
    dfs(0,0);
 
    if (answer == 1000) printf("-1\n");
    else if (answer == 500) printf("0\n");
    else printf("%d\n", answer);
    return 0;
}

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
struct Birus {
    int r;
    int c;
    bool Alive;
    Birus() {};
    Birus(int r, int c, bool Alive) :r(r), c(c), Alive(Alive) {};
};
 
int N, M, cnt=0,answer = 1e9;
int b_cnt=0;
int map[51][51];
int isV[51][51];
int dr[] = {0,0,1,-1}, dc[] = {1,-1,0,0};
queue<pair<int, int> > q1;
vector<pair<int, int> >start_v;
vector<Birus> birus;
 
int bfs() {
    int time,b=b_cnt; //글로벌로 여러번 실행되면 데이터를 해줄때마다 초기화해주어야한다.(까먹기쉬움)
    memset(isV, 0, sizeof(isV));
    for (int i = 0; i < M; i++) {
        q1.push(make_pair(start_v[i].first,start_v[i].second));
        isV[start_v[i].first][start_v[i].second]=1; //방문
    }
 
    while (!q1.empty()) {
        int nr = q1.front().first, nc = q1.front().second;
        q1.pop();
        time = isV[nr][nc]-1;
        
        for (int i = 0; i < 4; i++) {
            int nnr = nr + dr[i], nnc = nc + dc[i];
            if (nnr < 0 || nnc < 0 || nnr >= N || nnc >= N) continue;
            if (isV[nnr][nnc] == 0 && map[nnr][nnc] == 0) {
                q1.push(make_pair(nnr, nnc));
                isV[nnr][nnc] = isV[nr][nc] + 1;
                b--;
            }
            else if (isV[nnr][nnc] == 0 && map[nnr][nnc] == 2) { //비활성화바이러스
                if (b > 0) { //0이 남아있다면
                    q1.push(make_pair(nnr, nnc));
                    isV[nnr][nnc] = isV[nr][nc] + 1;
                }
                else {
                    isV[nnr][nnc] = isV[nr][nc];
                }
            }
        }
    }
    if (b == 0 && answer > time) answer = time; // 모두 탐색했고 최소를 구해준다.
}
 
void dfs(int start,int len) {
    if (len == M) { 
        //bfs gogo    
        bfs();
        return; 
    }
 
    for (int i = start; i < birus.size(); i++) {
        if (birus[i].Alive == false) {
            birus[i].Alive = true;
            start_v.push_back(make_pair(birus[i].r,birus[i].c)); //바이러스 선택
            dfs(i,len + 1); //뒤로만 진행하기위해서 (순열과 조합의 차이)
            birus[i].Alive = false; /// ***dfs재귀의 기본구조***
            start_v.pop_back();
        }
    }
}
 
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) { 
        for (int j = 0; j < N; j++) { 
            cin >> map[i][j];
            if (map[i][j] == 0) b_cnt++; //감염되어야 하는 '0'의 수
            if (map[i][j] == 2) { birus.push_back(Birus(i, j, false)); } //바이러스 정보 대입
        }
    }
 
    dfs(0,0);
 
    printf("%d\n", answer == 1e9 ? -1 : answer); //answer이 1e9이면 -1출력 아니면 answer출력
    return 0;
}