[백준 17141] 연구소 2

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct data{int x,y;};
queue<data> q;
vector<data> v;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
int arr[51][51], check[51][51];
int n,m,ans=102, temp, flag, cnt;
void check_time(){
    temp=0, flag=0, cnt;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(check[i][j]==-1) {
                flag=1;
                break;
            }
            if (temp!=-1 && check[i][j]>=temp)
                temp=check[i][j];
        }
    }
}
void bfs() {
    // 일단 원본 복사
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            // 벽이면 -2로 해놓고
            if(arr[i][j]==1)
                check[i][j]=-2;
            // 아닌 곳들은 -1 (0인 빈칸이나 바이러스가 이동할 수 있는 2인 곳들)
            else
                check[i][j]=-1;
        }
    }
    
    // 고른 m개의 위치에 바이러스 놓기
    for(int i=0; i<v.size(); i++) {
        int x = v[i].x;
        int y = v[i].y;
        check[x][y]=0;
        q.push({x,y});
    }
    
    // 바이러스 퍼트리기
    while(!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        
        for(int k=0; k<4; k++) {
            int nx=x+dx[k];
            int ny=y+dy[k];
            
            if(0<=nx && nx<n && 0<=ny && ny<n) {
                // 바이러스가 퍼지지 않았거나
                // 바이러스가 퍼지긴 했는데 더 짧은 시간에 퍼질 수 있다면
                if(check[nx][ny]==-1 || check[nx][ny]>check[nx][ny]+1) {
                    check[nx][ny]=check[x][y]+1;
                    q.push({nx,ny});
                }
            }
        }
    }
    // 퍼진 시간 체크
    check_time();
}
void dfs(int cx, int cy, int cnt) {
    if(cnt==m) {
        bfs();
        if (flag==1 && ans==102) ans=102;
        else if(flag==0 && ans>temp)
            ans=temp;
        return ;
    }
    
    if(cx>=n) return ;
    
    if(cy<n) {
        if(arr[cx][cy]==2) {
            v.push_back({cx,cy});
            dfs(cx, cy+1, cnt+1);
            v.pop_back();
            dfs(cx, cy+1, cnt);
        } else {
            dfs(cx,cy+1,cnt);
        }
    } else {
        dfs(cx+1,0,cnt);
    }
}
int main(void) {
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%d", &arr[i][j]);
    
    dfs(0,0,0);
    if(ans==102)
        printf("-1");
    else
        printf("%d", ans);
    return 0;
}

별로 잘 작성한 코드는 아니라고 생각하지만 그래도 풀었으니까 뿌듯해서 올린다ㅠㅠ 생각한 알고리즘은

1. 배열의 크기와 바이러스를 놓을 수 있는 갯수 입력받기

2. 배열을 전체적으로 전부 도는데 숫자가 2인 곳 (바이러스를 놓을 수 있는 곳) m개 뽑기

  2.1. m개 뽑았으면 bfs 돌리면서 바이러스를 퍼트려보기

     2.1.1 바이러스를 다 퍼트렸는데 만약 배열에 -1이 있다면 temp = -1

     2.1.2 바이러스를 다 퍼트렸는데 -1이 없다면

     2.1.2.1 temp = 바이러스르 퍼트리는데 걸리는 최소 시간

  2.2 기존에 걸렸던 최소시간보다 새로 고른 m개에서 바이러스를 퍼트리는데 걸리는 시간이 더 길다면

     2.2.1 ans=temp

이거였는데  예제 5번에서 답이 계속 틀려서 생각해보니까

1. 모든 경우에서 -1이 나올 경우

2. 모든 경우에서 -1이 안나올 경우

3. 일부 경우에서 -1이 나올 경우

3번에서 ans=-1로 되어서 그 뒤에 최소시간을 찾아도 -1로 출력되었다.

그래서 경우의 수에서 -1이 나오더라도 ans(바이러스를 퍼트리는데 걸리는 최소시간)가 한번이라도 나왔다면 ans를 출력하면 된다고 생각했는데 아무리 머리를 굴려봐도 제대로 안 굴러가서 결국엔 백준 슬랙에 물어봤다.

답변으로

-1을 출력하는 건 그냥 출력을 그렇게 하면 되는 거니까 그 값에 너무 신경쓸 필요가 없습니다

단 하나라도 되기만 하면 답이 -1이 아니니까

충분히 큰 수로 ans를 설정해놓고 전체에 퍼뜨릴 수 있는 경우에만 답을 갱신하면

끝까지 처음 상태로 남아있으면 -1을 출력해버리면 되겠죠?

이렇게 알려주셨고 결국엔 코드 고쳐서 제출했다. 

여전히 삽질 많이하고 계속 헤매고 있긴한데 그래도 조금씩 나아지고 있는 것 같다.

질문 안하고 혼자서 풀 수 있을 때까지 더 열심히 해야지!