백준(boj) 17142 연구소3 (파이썬, c++)

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

풀이

---

바이러스가 있는 곳을 리스트에 표시해두고, 완전 탐색 하였다. 시작할 때 빈칸들을 세어두고, 확산할 때마다 cnt 변수를 1씩 늘려줘서 cnt가 빈칸의 개수가 되면 바이러스가 다 퍼진 것으로 return 해주었다. BFS를 사용하여 퍼지는 속도를 균일하게 만들어, 마지막에 퍼진 것이 제일 늦게 퍼진 것이다.

python3

from sys import*
from collections import*
input = stdin.readline
def cal():
    q=deque()
    cnt=0
    visit=[[0]*n for _ in range(n)]
    for x, y in temp:
        q.append((0,x,y))       #시간, 좌표
        visit[x][y]=1
    while q:
        t, x, y = q.popleft()
        for dx, dy in dd:
            nx, ny = x+dx, y+dy
            if nx<0 or ny<0 or nx>n-1 or ny>n-1 or visit[nx][ny]\
               or a[nx][ny]==1:continue
            if not a[nx][ny]:
                cnt+=1
                if cnt == zero_cnt: return t+1
            visit[nx][ny]=1
            q.append((t+1, nx, ny ))
    return INF
def solve(pos, cnt):
    res = INF
    if cnt > m: return res
    if pos == len(virus_list):
        if cnt == m:
            res = min(res, cal())
        return res
    temp.append(virus_list[pos])
    res = min(res, solve(pos+1, cnt+1))
    temp.pop()
    res = min(res, solve(pos+1, cnt))
    return res
n,m=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(n)]
temp=[]
INF=1e9
virus_list = []
zero_cnt = 0
dd=[(-1,0),(1,0),(0,-1),(0,1)]
for i in range(n):
    for j in range(n):
        if not a[i][j]: zero_cnt+=1
        elif a[i][j]==2: virus_list.append((i, j))
ans=solve(0,0)
if zero_cnt ==0: print(0)
else: print(ans if ans!=INF else -1)

C++

#include<cstdio>
#include<tuple>
#include<queue>
#include<memory.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef tuple<int, int, int> T;
typedef pair<int, int> P;
const int INF = 1e9, SIZE = 51;
int zero_cnt=0, n, m;
int a[SIZE][SIZE], visit[SIZE][SIZE];
vector<P> temp, virus_list;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int cal(){
    queue<T> q;
    int cnt=0;
    memset(visit, 0, sizeof(visit));
    for(int i=0; i<temp.size(); i++){
        int x, y;
        x = temp[i].first, y = temp[i].second;
        q.push(make_tuple(0, x, y));
        visit[x][y] = 1;
    }
    while(!q.empty()){
        int t, x, y;
        tie(t, x, y) = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int nx, ny;
            nx = x+dx[i], ny = y+dy[i];
            if(nx<0 || ny<0 || nx>n-1 || ny>n-1 || visit[nx][ny] || a[nx][ny]==1) continue;
            if (!a[nx][ny]){
                cnt++;
                if(cnt == zero_cnt) return t+1;
            }
            visit[nx][ny]=1;
            q.push(make_tuple(t+1, nx, ny));
        }
    } 
    return INF;
}
int solve(int pos, int cnt){
    int res = INF;
    if(cnt>m) return res;
    if(pos == virus_list.size()){
        if(cnt == m) res = min(res, cal());
        return res;
    }
    int x, y;
    x = virus_list[pos].first;
    y = virus_list[pos].second;
    temp.push_back({x, y});
    res = min(res, solve(pos+1, cnt+1));
    temp.pop_back();
    res = min(res, solve(pos+1, cnt));
    return res;
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
            scanf("%d", &a[i][j]);
            if(!a[i][j]) zero_cnt++;
            else if(a[i][j]==2) virus_list.push_back({i, j});
        }
    int ans = solve(0, 0);
    if(zero_cnt==0) printf("0");             //바이러스 퍼질곳이 없는경우
    else printf("%d", ans!=INF? ans: -1);    //INF면 못채운거, -1 출력 
    return 0; 
}

고찰

---

c++ vector는 pop()이 아니고 pop_back();