[백준] 14502 연구소(C++)

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

14502번: 연구소

---

난이도 : 골드 5

 

풀이 과정 :

최근에 코테를 몇번 참가해보면서 구현을 정확하고 빠르게 푸는 것의 중요성을 깨달았다.

이 문제는 구현+bfs인데, 백준에서 bfs문제중 바이러스 문제가 있어서 그거 먼저 풀면 도움이 될듯하다.

n과 m이 최대 8까지기 때문에 완탐! 으로 가능하다 

왜냐면 0이나올수 있는 곳에 벽 3개를 두는 것이기 때문에 최대 64C3 번 연산 이기 때문

관건은 벽 3개를 두는 방법을 어떻게 구현하는 가인데 그냥 고민하다가 6중반복문을 이용해서 해봤다..

만약 세 좌표중 두개 같으면 넘어가고, 세개 다 다른 좌표이고, 0일때만 bfs가 돌아가도록 하였음

 

코드 :

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int n, m, arr[10][10], arr2[10][10], ans;
int dx[4] = { 0, 0, 1, -1};
int dy[4] = { 1, -1, 0, 0 };

queue<pair<int,int>> q;
int bfs(){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j] == 2) q.push(make_pair(i,j));
        }
    }
    while (!q.empty()) {
        int xx=  q.front().first;
        int yy = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = xx + dx[i];
            int ny = yy + dy[i];
            if (ny >= 0 && nx >= 0 && nx < n && ny < m && arr2[nx][ny] == 0) {
                arr2[nx][ny] = 2;
                q.push(make_pair(nx, ny));                  
            }
        }
    }   
    int cnt = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr2[i][j] == 0) cnt++;
        }
    }  
    return cnt;
}

int main()
{   
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> arr[i][j];
        }
    }
    
    for(int x1=0;x1<n;x1++){
        for(int y1=0;y1<m;y1++){
            for(int x2=0;x2<n;x2++){
                for(int y2=0;y2<m;y2++){
                    for(int x3=0;x3<n;x3++){
                        for(int y3=0;y3<m;y3++){
                            if((x1==x2 && y1==y2) || (x2==x3 && y2==y3) || (x1==x3 && y1==y3)) continue;
                            if(arr[x1][y1] == 0 && arr[x2][y2] ==0 && arr[x3][y3] == 0){                                
                                copy(&arr[0][0], &arr[0][0]+100, &arr2[0][0]);
                                arr2[x1][y1] =1, arr2[x2][y2] =1, arr2[x3][y3] =1;
                                ans = max(bfs(), ans);
                            }
                        }
                    }
                }
            }
        }
    }    
    cout << ans;   
}