백준 연구소 시리즈

14502 연구소
17141 연구소2
17142 연구소3

• 주어진 바이러스 중에서 M개를 고를 때 백트래킹
• 빈칸에 바이러스가 퍼지는 시간 구할 때 BFS를 사용한다.

연구소

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 배열을 사용하지 않고 백트래킹을 시도하면 시간초과가 났었다

연구소2

#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)

연구소3

#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)에 퍼지는 시간만 계산한다.