OJ 17142 : 연구소 3 - C++
연구소 3
코드
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 1237 ~ 0109
// 10C5 = 252 * 2500 = 630,000
int N,M,ans=1e9;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int board[55][55];
int tmp[55][55];
int cost[55][55];
vector<pair<int,int>> virus;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
cin >> board[i][j];
if(board[i][j] == 2)
virus.push_back({i,j});
}
int ch[virus.size()];
fill(ch, ch+virus.size(), 1);
for(int i=0;i<M;i++) ch[i] = 0;
do{
queue<pair<int,int>> q;
for(int i=0;i<N;i++)
{
fill(cost[i], cost[i]+N, -1);
for(int j=0;j<N;j++)
tmp[i][j] = board[i][j];
}
for(int i=0;i<virus.size();i++)
if(ch[i] == 0)
{
tmp[virus[i].first][virus[i].second] = 8;
q.push(virus[i]);
cost[virus[i].first][virus[i].second] = 0;
}
int MIN = 0;
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
if(cost[ny][nx] >= 0 or tmp[ny][nx] == 1) continue;
cost[ny][nx] = cost[cur.first][cur.second] + 1;
q.push({ny,nx});
if(tmp[ny][nx] != 2)
MIN = max(MIN, cost[ny][nx]);
tmp[ny][nx] = 8;
}
}
bool flag = true;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(cost[i][j] == -1 and tmp[i][j] != 1) {
flag = false;
goto stop;
}
}
stop:;
if(flag == true) ans = min(ans, MIN);
}while(next_permutation(ch, ch+virus.size()));
if(ans != 1e9)
cout << ans;
else
cout << -1;
return 0;
}
- 핵심
: next_permutation
을 이용해서 전체 virus개수
중 M개를 선택
하는 조합
을 모두에 대해 전부 바이러스를 퍼뜨리는 경우
중 최소값
을 기록
- 시간복잡도
- 최대
10개
의 바이러스
중 5개를 선택
하는 수이기 때문에 252가지 경우
를 가진다
252가지 경우
에 대해 BFS를 수행
해서 총 252*(N^2)
= 약 630,000
번 연산 수행하니까 충분!
Author And Source
이 문제에 관하여(OJ 17142 : 연구소 3 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-17142-연구소-3-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <cstdio> #include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #include <set> #include <deque> #include <numeric> #include <map> #define ll long long using namespace std; // 1237 ~ 0109 // 10C5 = 252 * 2500 = 630,000 int N,M,ans=1e9; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int board[55][55]; int tmp[55][55]; int cost[55][55]; vector<pair<int,int>> virus; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; for(int i=0;i<N;i++) for(int j=0;j<N;j++) { cin >> board[i][j]; if(board[i][j] == 2) virus.push_back({i,j}); } int ch[virus.size()]; fill(ch, ch+virus.size(), 1); for(int i=0;i<M;i++) ch[i] = 0; do{ queue<pair<int,int>> q; for(int i=0;i<N;i++) { fill(cost[i], cost[i]+N, -1); for(int j=0;j<N;j++) tmp[i][j] = board[i][j]; } for(int i=0;i<virus.size();i++) if(ch[i] == 0) { tmp[virus[i].first][virus[i].second] = 8; q.push(virus[i]); cost[virus[i].first][virus[i].second] = 0; } int MIN = 0; while(!q.empty()) { auto cur = q.front(); q.pop(); for(int dir=0;dir<4;dir++) { int ny = cur.first + dy[dir]; int nx = cur.second + dx[dir]; if(nx<0 or ny<0 or nx>=N or ny>=N) continue; if(cost[ny][nx] >= 0 or tmp[ny][nx] == 1) continue; cost[ny][nx] = cost[cur.first][cur.second] + 1; q.push({ny,nx}); if(tmp[ny][nx] != 2) MIN = max(MIN, cost[ny][nx]); tmp[ny][nx] = 8; } } bool flag = true; for(int i=0;i<N;i++) for(int j=0;j<N;j++) { if(cost[i][j] == -1 and tmp[i][j] != 1) { flag = false; goto stop; } } stop:; if(flag == true) ans = min(ans, MIN); }while(next_permutation(ch, ch+virus.size())); if(ans != 1e9) cout << ans; else cout << -1; return 0; }
- 핵심
:next_permutation
을 이용해서전체 virus개수
중M개를 선택
하는조합
을 모두에 대해전부 바이러스를 퍼뜨리는 경우
중최소값
을 기록
- 시간복잡도
- 최대
10개
의바이러스
중5개를 선택
하는 수이기 때문에252가지 경우
를 가진다252가지 경우
에 대해BFS를 수행
해서 총252*(N^2)
=약 630,000
번 연산 수행하니까충분!
Author And Source
이 문제에 관하여(OJ 17142 : 연구소 3 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-17142-연구소-3-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)