14502 연구소
17141 연구소2
17142 연구소3
from collections import deque
empty = []
virusList = []
used = [False] * 64
queue = deque()
res = 0
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
def safe(vis):
global n, m, res
size = 0
for i in range(n):
for j in range(m):
if vis[i][j] == 0 and board[i][j] == 0:
size += 1
res = max(res, size)
def virus():
global n,m
vis = [[0] * m for _ in range(n)]
for v in virusList:
queue.append(v)
while queue:
curX, curY = queue.popleft()
vis[curX][curY] = 1
for dir in range(4):
nx = curX + dx[dir]
ny = curY + dy[dir]
if nx<0 or nx >= n or ny < 0 or ny >= m:
continue
if board[nx][ny] == 0 and vis[nx][ny] == 0:
queue.append([nx,ny])
vis[nx][ny] = 1
safe(vis)
def make_wall(depth, i):
global res
if depth == 3:
virus()
return
for wall in range(i, len(empty)):
if not used[wall]:
curX, curY = empty[wall]
used[wall] = 1;
board[curX][curY] = 1
make_wall(depth+1, wall)
board[curX][curY] = 0
used[wall] = 0
n, m = map(int, input().split())
board = []
for i in range(n):
board.append(list(map(int, input().split())))
vis = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if board[i][j] == 0:
empty.append([i,j])
elif board[i][j] == 2:
virusList.append([i,j])
make_wall(0, 0)
print(res)
나는 used 배열을 사용하지 않고 백트래킹을 시도하면 시간초과가 났었다
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <limits.h>
#include <algorithm>
using namespace std;
int n, m; // n : 연구소 크기, m : 바이스러 개수
int map[51][51]; // 0 빈칸, 1 벽, 2 바이러스
int dist[51][51];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0 ,1, 0};
vector<pair<int ,int> > virus;
vector<pair<int, int> > selected;
int ans = INT_MAX;
bool used[10];
queue<pair<int ,int> > q;
void spread()
{
while(!q.empty())
q.pop();
memset(dist, 0 , sizeof(dist));
int mx = 1;
for(int i = 0; i < selected.size(); i++)
{
q.push(selected[i]);
dist[selected[i].first][selected[i].second] = 1;
}
while(!q.empty())
{
pair<int ,int> cur = q.front();
q.pop();
for(int dir = 0; dir < 4; dir++)
{
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue ;
if(dist[nx][ny] || map[nx][ny] == 1) continue ;
q.push({nx, ny});
dist[nx][ny] = dist[cur.first][cur.second] + 1;
mx = max(mx, dist[nx][ny]);
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(map[i][j] == 0 && dist[i][j] == 0)
return ;
ans = min(ans, mx-1);
}
void DFS(int depth)
{
if(selected.size() == m)
{
spread();
return ;
}
for(int i = depth; i < virus.size(); i++)
{
if(!used[i])
{
selected.push_back(virus[i]);
used[i] = 1;
DFS(i + 1);
used[i] = 0;
selected.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] == 2)
virus.push_back({i,j});
}
}
DFS(0);
if(ans == INT_MAX)
cout << -1;
else
cout << ans;
}
파이썬 코드
import sys
from collections import deque
from itertools import combinations
virus_list = []
used = [0] * 10
selected = []
dx = [0, 1 ,0 ,-1]
dy = [-1, 0, 1, 0]
mx = 0
res = 2147483647
n, m = map(int, input().split())
board =[list(map(int, sys.stdin.readline().split())) for _ in range(n)]
for i in range(n):
for j in range(n):
if board[i][j] == 2:
virus_list.append([i,j]) # 바이러스를 놓을 수 있는 곳 저장
def spread(virus):
global res
mx = 1
q = deque()
dist = [[0] * n for _ in range(n)]
for selected in virus:
q.append(selected)
dist[selected[0]][selected[1]] = 1
while q:
curX, curY = q.popleft();
for dir in range(4):
nx = curX + dx[dir]
ny = curY + dy[dir]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if board[nx][ny] == 1 or dist[nx][ny] :
continue
q.append([nx,ny])
dist[nx][ny] = dist[curX][curY] + 1
mx = max(dist[nx][ny], mx)
for i in range(n):
for j in range(n):
if board[i][j] == 0 and dist[i][j] == 0: # 빈칸인데 바이러스를 퍼뜨리지 못한 경우 그냥 return
return
res = min(res, mx-1)
def DFS(depth):
for virus in list(combinations(virus_list, m)): # 바이러스 리스트에서 m개를 뽑아 바이러스를 퍼뜨리기
spread(virus)
DFS(0)
if res == 2147483647: # res가 한번도 갱신된적없이 그대로이면 어떤 경우에도 바이러스를 퍼뜨릴 수 없었다는 뜻
print(-1)
else:
print(res)
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <limits.h>
#include <algorithm>
using namespace std;
int n, m; // n : 연구소 크기, m : 바이스러 개수
int map[51][51]; // 0 빈칸, 1 벽, 2 바이러스
int dist[51][51];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0 ,1, 0};
vector<pair<int ,int> > virus;
vector<pair<int, int> > selected;
int ans = INT_MAX;
bool used[10];
queue<pair<int ,int> > q;
void spread()
{
while(!q.empty())
q.pop();
memset(dist, 0 , sizeof(dist));
int mx = 1;
for(int i = 0; i < selected.size(); i++)
{
q.push(selected[i]);
dist[selected[i].first][selected[i].second] = 1;
}
while(!q.empty())
{
pair<int ,int> cur = q.front();
q.pop();
for(int dir = 0; dir < 4; dir++)
{
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue ;
if(dist[nx][ny] || map[nx][ny] == 1) continue ;
q.push({nx, ny});
dist[nx][ny] = dist[cur.first][cur.second] + 1;
if(map[nx][ny] == 0) // ⭐️주의
mx = max(mx, dist[nx][ny]);
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(map[i][j] == 0 && dist[i][j] == 0)
return ;
ans = min(ans, mx-1);
}
void DFS(int depth)
{
if(selected.size() == m)
{
spread();
return ;
}
for(int i = depth; i < virus.size(); i++)
{
if(!used[i])
{
selected.push_back(virus[i]);
used[i] = 1;
DFS(i + 1);
used[i] = 0;
selected.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] == 2)
virus.push_back({i,j});
}
}
DFS(0);
if(ans == INT_MAX)
cout << -1;
else
cout << ans;
}
⭐️주의
비활성 바이러스는 이미 바이러스기 때문에 바이러스가 퍼지는 시간에 계산하지 않는다. 빈공간(map[nx][ny] == 0)에 퍼지는 시간만 계산한다.