백준(boj) 14502_연구소 (파이썬, c++)

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

풀이

---

벽을 3개 세워서 바이러스들이 퍼지게 한다. 바이러스가 퍼지지 않는 곳이 최대가 되도록 벽을 세운다. 6중 포문으로 3개의 벽의 위치를 나타내었고, 바이러스가 퍼지는 것은 바이러스들을 리스트에 넣어놓고 bfs()를 돌릴 때마다 큐에 바이러스들을 넣고 퍼지도록 만들었다.

벽을 세 개 놓을 때 겹쳐서 놓지 않도록 (ix==jx and iy==jy) or (ix==kx and iy==ky) or (jx==kx and jy==ky) 인 경우는 continue로 건너뛰어 준다. bfs()함수에서 퍼지지 않는 바이러스 값을 찾을 때는 마지막에 a를 이중 포문으로 돌면서 0인 곳의 개수를 세어줘도 좋지만, 시간을 단축하기 위해서 zero 변수를 만들어서 0의 개수를 저장해놓고, bfs()에서 바이러스가 번식할 때마다 세어준 cnt 값을 빼줌으로써 퍼지지 않은 개수를 구하였다.

python3(PyPy3로 제출)

from sys import*
from collections import*
input = stdin.readline
​
def bfs():
    q=deque()
    visit=[[0]*m for _ in range(n)]
    for x, y in virus:
        q.append((x, y))
        visit[x][y]=1
    cnt=0
    while q:
        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>m-1 or visit[nx][ny] or a[nx][ny]!=0: continue
            visit[nx][ny]=1
            cnt += 1
            q.append((nx, ny))
    return zero - cnt
​
n,m = map(int,input().split())
a=[]; zero=-3   #벽 3개 세울거라 3개 미리 빼줌
virus=[]; res=0
dd=[(-1,0), (0,1), (1,0), (0,-1)]
for i in range(n):
    a.append(list(map(int,input().split())))
    for j in range(m):
        if a[i][j] == 2:
            virus.append((i,j))
        elif a[i][j]==0:
            zero += 1
for ix in range(n):
    for iy in range(m):
        for jx in range(n):
            for jy in range(m):
                if ix==jx and iy==jy: continue
                for kx in range(n):
                    for ky in range(m):
                        if (kx==jx and ky==jy) or (kx==ix and ky==iy): continue
                        if not (a[ix][iy] or a[jx][jy] or a[kx][ky]):       #전부 0이면
                            a[ix][iy], a[jx][jy], a[kx][ky] = 1, 1, 1
                            res = max(res, bfs())
                            a[ix][iy], a[jx][jy], a[kx][ky] = 0, 0, 0
print(res)

C++

#include<cstdio>
#include<memory.h>
#include<algorithm>
#include<queue>
​
using namespace std;
const int SIZE = 8;
typedef pair<int, int> P;
​
vector<P> virus;
int dd[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int zero=-3, n, m;
int a[SIZE][SIZE], visit[SIZE][SIZE];
​
int bfs(){
    queue<P> q;
    memset(visit, 0, sizeof(visit));
    for(auto v: virus){
        int x, y;
        x = v.first;
        y = v.second;
        q.push({x, y});
        visit[x][y]=1;
    }
    int cnt=0;
    while(!q.empty()){
        int x, y;
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(auto v: dd){
            int dx, dy, nx, ny;
            dx = v[0];
            dy = v[1];
            nx = x+dx, ny = y+dy;
            if(nx<0 || ny<0 || nx>n-1 || ny>m-1 || visit[nx][ny] || a[nx][ny]!=0) continue;
            visit[nx][ny]=1;
            cnt++;
            q.push({nx, ny});
        }
    }
    return zero - cnt;
}
​
int main(){
    scanf("%d %d",&n, &m);
    int res=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d",&a[i][j]);
            if(a[i][j] == 2) virus.push_back({i, j});
            else if(a[i][j]==0) zero++;
        }
    }
    for(int ix=0; ix<n; ix++){
        for(int iy=0; iy<m; iy++){
            for(int jx=0; jx<n; jx++){
                for(int jy=0; jy<m; jy++){
                    if(ix==jx && iy==jy) continue;
                    for(int kx=0; kx<n; kx++){
                        for(int ky=0; ky<m; ky++){
                            if((kx==jx && ky==jy) || (kx==ix && ky==iy)) continue;
                            if (!(a[ix][iy] || a[jx][jy] || a[kx][ky])){
                                a[ix][iy] = a[jx][jy] = a[kx][ky] =1;
                                res = max(res, bfs());
                                a[ix][iy] = a[jx][jy] = a[kx][ky] =0;
                            }
                        }
                    }
                }
            }
        }
    }
    printf("%d",res);
    return 0;
}

고찰

---

.