백준 14502, 17141, 17142 연구소 문제풀이
연구소, 연구소 2, 연구소 3 문제풀이
연구소
개인적으로 재밌던 문제다.
그래프 문제가 손에 익기 시작하면서 다른 코드를 참조하지 않고 쉽게 풀었기 때문에 재미가 확 붙었던 것 같다.
연구소 1 분석
먼저 연구소 1번 문제는 바이러스의 위치와 벽의 위치가 정해져있다. 벽의 위치를 잘 찾아서 얻을 수 있는 안전 영역의 최대 크기를 출력해야한다. 첫째, 벽을 꼭 3개 세워야 한다.
지도의 크기가 크지 않으므로 모든 경우의 수를 다 해본다.
O((NM)^3)*O(NM) = O(NM^4) = 16,777,216가지. 충분하다.
충분하다의 기준은 정확한 수는 아니지만 1억=1초라고 봐도 무방하다.
둘째, 벽을 세우고 난 후에 어떤 탐색이든 상관 없다. 바이러스가 지나간 곳을 모두 칠해준다.
주의할 점은 여러 경우의 수를 해봐야 하기 때문에 매번 새로운 배열변수에 copy해야한다. 나의 경우엔 원래 맵은 ma, 복사된 배열은 copymap으로 저장해주었다.
셋째, 탐색 한 후에 안전영역 크기를 구해준다.
0인곳을 찾아 count해주면 된다. 함수를 호출할 때마다 최대 크기가 바뀌므로 max(함수 return값,ans) 해준다.
연구소 1 소스
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,int>> candi;
int copymap[10][10]={0};
int ma[10][10]={0};
int x_index[4]={-1,1,0,0};
int y_index[4]={0,0,-1,1};
int cal(){
int virus_x;
int virus_y;
for(auto virus:candi){
queue<pair<int,int>> q;
q.push(virus);
while(!q.empty()){
tie(virus_x,virus_y)=q.front(); q.pop();
int nx,ny;
for(int i=0;i<4;i++){
nx=virus_x+x_index[i];
ny=virus_y+y_index[i];
if(copymap[nx][ny]==0&&nx>=0&&nx<n&&ny>=0&&ny<m)
{
copymap[nx][ny]=1;
q.push(make_pair(nx,ny));
}
}
}
}
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(copymap[i][j]==0)
cnt++;
}
}
return cnt;
}
int go(int index,int start){
if(index==3)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
copymap[i][j]=ma[i][j];
}
}
return cal();
}
int ans=0;
for(int i=start;i<n*m;i++){
int x=i/m;
int y=i%m;
if(ma[x][y]==0)
{
ma[x][y]=1;
ans=max(ans,go(index+1,i+1));
ma[x][y]=0;
}
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>ma[i][j];
if(ma[i][j]==2){
candi.push_back(make_pair(i,j));
}
}
}
cout<<go(0,0)<<'\n';
}
연구소 2 분석
연구소 1과 약간 다르다. 벽을 세우지 않고, 입력 2는 바이러스가 아니고 바이러스가 될 수 있는 후보이다.
연구실의 모든 칸에 바이러스가 있게 되는 최소 시간을 출력하고, 그럴 수 없는 경우에는 -1을 출력하는 문제다.
첫째, 모든 바이러스 중 3가지를 고른다.
내 경우엔 vector<pair<int,int>> candi 를 이용했는데, 1차원 배열이 2차원 배열보다 n가지 고르기가 쉽기 때문에 1차원 배열을 이용했다.
둘째, bfs탐색을 이용해 갈 수 있는 모든 곳을 거리로 표시한다.
다만 주의할 점은 큐에 바이러스 세개 모두 먼저 넣어준 뒤에 bfs탐색을 시작한다. 만약 큐에 첫번째 바이러스만 넣고 탐색하면 첫번째 바이러스가 이동할 수 있는 모든 곳을 이동 한 뒤에 두번째 바이러스가 활성화하게 된다.
셋째, 각 return 값의 min값을 출력한다.
연구소 2 소스
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,int>> candi;
int copymap[60][60]={0};
int ma[60][60]={0};
vector<pair<int,int>> virus;
int x_index[4]={-1,1,0,0};
int y_index[4]={0,0,-1,1};
int cal(){
int virus_x;
int virus_y;
int d[60][60]={0};
queue<pair<int,int>> q;
for(auto vi:virus)
q.push(vi);
while(!q.empty()){
tie(virus_x,virus_y)=q.front(); q.pop();
int nx,ny;
for(int i=0;i<4;i++){
nx=virus_x+x_index[i];
ny=virus_y+y_index[i];
if(d[nx][ny]==0&©map[nx][ny]!=1&©map[nx][ny]!=2&&nx>=0&&nx<n&&ny>=0&&ny<n)
{
d[nx][ny]=d[virus_x][virus_y]+1;
q.push(make_pair(nx,ny));
}
}
}
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cnt=max(cnt,d[i][j]);
if(d[i][j]==0&©map[i][j]!=2&©map[i][j]!=1)
return -1;
}
}
return cnt;
}
int go(int start,int index){
if(index==m){
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
copymap[i][j]=ma[i][j];
}
}
for(auto vi:virus)
{
copymap[vi.first][vi.second]=2;
}
return cal();
}
int ans=2100000000;
for(int i=start;i<candi.size();i++)
{
//cout<<candi[i].first<<candi[i].second<<endl;
virus.push_back(candi[i]);
int tmp=go(i+1,index+1);
if(tmp!=-1)
ans=min(tmp,ans);
virus.pop_back();
}
if(ans==2100000000)
return -1;
return ans;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>ma[i][j];
if(ma[i][j]==2){
candi.push_back(make_pair(i,j));
ma[i][j]=0;
}
}
}
cout<<go(0,0)<<'\n';
}
연구소 3 분석
연구소 2와 거의 유사한 문제다.
다른 점은 연구소 2는 바이러스를 고르지 않으면 그냥 0으로 생각하면 되는데,
연구소 3은 잠재 바이러스이기 때문에 굳이 거기까지 도달하지 않아도 함수가 끝나야 한다.
이걸 어떻게 해결할까 고민을 많이 하다가 몇번 시행착오 후 반례를 찾아본 뒤에 알게 되었는데,
5 3
2 2 2 0 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
answer : 2
4 2
0 1 1 0
2 1 1 2
2 1 1 2
0 1 1 0
answer : 2
5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 0 0 2 0
1 1 1 1 1
answer : 2
이 세 반례가 도움이 되었다.
바로 내 코드는 바이러스->2가 이동이 안되게 했고, 그렇게 하니 첫번째는 맞고, 두번째는 틀렸다.
당연하지만 반례를 보기 전엔 몰랐다.
두번째 시도에선 바이러스->2가 이동이 되게 했다. 이번엔 1번이 틀렸다.
이건 연구소2번 문제와 동일하게 풀었기 때문이다.
세번째 시도에선 바이러스->2가 이동이 되게 하지만 시간은 그대로이게 풀었다. 이번엔 2번이 틀렸다.
엄연히 바이러스->잠재바이러스도 1초가 지나가기 때문이다.
결론 바이러스->빈칸, 바이러스->바이러스 모두 시간은 더해주되 바이러스가 비활성화된 곳은 마지막에 최대 시간을 구할 때 제외시켜 주면 된다. 연구소 2 코드에서 반례가 추가되는 것은 마지막에 잠재 공간이 더해지는 것 때문에 틀린 것이기 때문이다.
오타, 질문, 지적 댓글로 남겨주세요.
연구소 3 소스
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int>> candi;
int copymap[60][60] = { 0 };
int ma[60][60] = { 0 };
vector<pair<int, int>> virus;
int x_index[4] = { -1,1,0,0 };
int y_index[4] = { 0,0,-1,1 };
int cal() {
int virus_x;
int virus_y;
int d[60][60] = { 0 };
queue<pair<int, int>> q;
for (auto vi : virus)
q.push(vi);
while (!q.empty()) {
tie(virus_x, virus_y) = q.front(); q.pop();
int nx, ny;
for (int i = 0; i < 4; i++) {
nx = virus_x + x_index[i];
ny = virus_y + y_index[i];
if (d[nx][ny] == 0 && copymap[nx][ny] != 1 && copymap[nx][ny] != 2 && nx >= 0 && nx < n&&ny >= 0 && ny < n)
{
d[nx][ny] = d[virus_x][virus_y] + 1;
q.push(make_pair(nx, ny));
}
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(copymap[i][j] != 5)
cnt = max(cnt, d[i][j]);
if (d[i][j] == 0 && copymap[i][j] != 2 && copymap[i][j] != 5 && copymap[i][j] != 1)
return -1;
}
}
return cnt;
}
int go(int start, int index) {
if (index == m) {
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
copymap[i][j] = ma[i][j];
}
}
for (auto vi : candi)
{
copymap[vi.first][vi.second] = 5;
}
for (auto vi : virus)
{
copymap[vi.first][vi.second] = 2;
}
return cal();
}
int ans = 2100000000;
for (int i = start; i < candi.size(); i++)
{
//cout<<candi[i].first<<candi[i].second<<endl;
virus.push_back(candi[i]);
int tmp = go(i + 1, index + 1);
if (tmp != -1)
ans = min(tmp, ans);
virus.pop_back();
}
if (ans == 2100000000)
return -1;
return ans;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> ma[i][j];
if (ma[i][j] == 2) {
candi.push_back(make_pair(i, j));
ma[i][j] = 0;
}
}
}
cout << go(0, 0) << '\n';
}
댓글남기기