[백준, c++] 14502 연구소

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

14502번: 연구소

bfs와 브루트포스를 사용해서 푸는 문제였다. 

먼저 벽을 세우고, 바이러스 개수만큼 bfs를 돌린 후, 0의 개수를 세는 방식으로 풀었다.  

3개의 벽을 세우는 것은 3중 for문으로 각기 다른 좌표들의 벽이 생성되게 했다. 

그리고, 바이러스의 위치를 bfs하기전 탐색하는 것보다 입력받을때 바이러스의 위치를  vector v에 추가해 이중 포문을 줄였다. 

 

놓쳤던 것을 몇가지 열거하자면, 

1. graph 에 입력을 받아놓고 그 graph배열 그대로 bfs를 돌렸던 것이다. (초기화가 안됬음)

내 bfs코드를 보면 graph[i][k]=2; 와 같이 graph의 값이 변화한다. 이러면 다음에 bfs를 돌릴 때 graph의 값이 변해있는 상태기 때문에 올바른 답이 출력되지 않는다. 그래서 graph2라는 graph의 복사 배열을 선언하고 bfs가 끝나면 graph2를 초기화한 다음, 다시 graph의 내용을 복사했다. 

2. b1,b2,b3,b4,b5,b6 가 서로 다 달라야 한다는 생각에 조건문을 

if((b1!=b3)&&(b2!=b4)&&(b3!=b5)&&(b4!=b6)&&(b1!=b5)&&(b2!=b6))로 작성했는데, 이렇게 할 경우 

(0,0), (1,1), (2,3)과 같이 다 다른 좌표들만 나오게 된다 우리가 원하는 것은 (0,1), (0,2), (2,2) 와 같이 x와 y 둘다 다른것이 아닌 하나만 다르면 출력되게 하는 것이므로 

if((b1!=b3||b2!=b4)&&(b3!=b5||b4!=b6)&&(b1!=b5||b2!=b6))  로 조건을 바꾼 후 해결했다. 

 

 

//
//  Copyright (c) 2021 HyeJin Shin All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
int N, M;
int graph[8][8];
int graph2[8][8];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
void bfs(int x, int y){
    queue<pair<int,int>> q;
    q.push({x,y});
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M)continue;
            if(graph2[nx][ny]==1)continue;
            if(graph2[nx][ny]==0){
                graph2[nx][ny]=2;
                q.push({nx,ny});
            }
        }
    }
    return ;
    
}

int zerocheck(){
    int cnt = 0;
    for(int i=0;i<N;i++){
        for(int k=0;k<M;k++){
            if(graph2[i][k]==0)cnt++;
        }
    }
    return cnt;
}
vector<pair<int, int>>v;
vector<pair<int,int>> g;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N>>M;
    int zero;
    int max = -1;
    for(int i=0;i<N;i++){  //입력받기
        for(int k =0;k<M;k++){
            cin >> graph[i][k];
            graph2[i][k]=graph[i][k];
            if(graph[i][k]==2){
                v.push_back({i,k});
            }
            else if(graph[i][k]==0){
                g.push_back({i,k});
                
            }
        }
    }
    for(int l=0;l<g.size();l++){
        int b1=g[l].first;
        int b2=g[l].second;
        for(int s=0;s<g.size();s++){
            int b3=g[s].first;
            int b4=g[s].second;
            for(int r=0;r<g.size();r++){
                int b5=g[r].first;
                int b6=g[r].second;
                if((b1!=b3||b2!=b4)&&(b3!=b5||b4!=b6)&&(b1!=b5||b2!=b6)){
                    graph2[b1][b2]=1;
                    graph2[b3][b4]=1;
                    graph2[b5][b6]=1;
                    for(int i=0;i<v.size();i++){  //바이러스 퍼뜨리기
                        int a = v[i].first;
                        int b = v[i].second;
                        bfs(a,b);
                    }
                    
                    zero = zerocheck();
                    if(zero>max){
                        max =zero;
                        }
                    
                    for(int kk=0;kk<8;kk++){
                        for(int ti=0;ti<8;ti++){
                            graph2[kk][ti]=0;
                        }
                    }
                    for(int bb=0;bb<N;bb++){
                        for(int nn=0;nn<M;nn++){
                            graph2[bb][nn]=graph[bb][nn];
                        }
                    }
                }  //if
            }
        }
        
    }
    cout<<max;
}

https://github.com/toki0411/BOJ/commit/4699b357c32d00f7f6ba81fb211545f591859169

연구소 · toki0411/BOJ@4699b35