[백준 14502번]연구소 with 삼성전자 SW역량테스트 문제

[백준 14502번]연구소 with 삼성전자 SW역량테스트 문제 BFS/Brute force

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

14502번: 연구소

 

배열이 주어지고 0은 빈 칸, 1은 벽, 2는 바이러스이고 바이러스는 인접한 배열(빈 캰)로 전염된다.

벽은 3개를 만들 수 있고 이 때 바이러스가 전염되지 않는 빈칸의 최대 개수를 출력해라

 

 

구현 아이디어

이 문제는 벽 3개가 설치되는 모든 경우의 수를 체크해야한다. 

주어진 배열의 크기가 3 <= N, M <= 8 이다. 

모든 경우의 수를 다 조합해 체크한다 해도 범위가 크지 않으니 시간초과 없이 풀 수 있을것이다.

전염되는 배열을 만드는 과정에서는 BFS로 구현해야하며 벽이 생길 수 있는 모든 경우의 수를 전부 체크해야하니 Brute force 두 가지 방식이 같이 쓰인다.

매번 벽을 설치하고 BFS를 통해 빈칸의 개수를 구하고 그 중 가장 큰 값을 출력하면 된다.

 

코드

#include <stdio.h>
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
using namespace std;

#define MAX 8

int map[MAX][MAX];
int n,m;

int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

void BFS(int ptrMap[][MAX], pair<int, int>start) // start는 바이러스의 위치
{
    queue<pair<int, int>>q;
    q.push(start);
    ptrMap[start.first][start.second]=2;
    
    while (!q.empty())
    {
        pair<int, int>x = q.front();
        q.pop();
        
        for(int i=0; i<4; i++)
        {
            if(x.first+dx[i]<0 || x.first+dx[i]>=n ||
               x.second+dy[i]<0 || x.second+dy[i]>=m) // 배열 밖인 경우 (범위 확인 필수)
                continue;
            
            if(ptrMap[x.first+dx[i]][x.second+dy[i]] == 0) // 빈 공간이면
            {
                int n_x = x.first+dx[i];
                int n_y = x.second+dy[i];
                ptrMap[n_x][n_y]=2; //감염
                
                q.push(make_pair(n_x, n_y));
            }
        }
    }
}

int solve(int ptrMap[][MAX])
{
    int result=0;
    int mapcopy[MAX][MAX];
    memcpy(mapcopy, ptrMap, sizeof(map)); // 다른 메모리에 카피
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(mapcopy[i][j]==2)
                BFS(mapcopy, make_pair(i, j));
        }
    }
  
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(mapcopy[i][j]==0)
                result++;
        }
    }
    
    return result;
}

int main()
{
    int result = 0; // 나올 수 없는 최대값으로 초기화
    cin>>n>>m;
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            int type=0;
            cin>>type;
            map[i][j] =type; // 0-빈칸, 1-벽, 2-바이러스
        }
    }
    
    int a=0, b=0, c=0; // 벽 3개
    while (a<n*m)
    {
        if(map[a/m][a%m]==0)
        {
            b = a+1;
            map[a/m][a%m] =1;
            while (b<n*m)
            {
                if(map[b/m][b%m] ==0)
                {
                    map[b/m][b%m] =1;
                    c= b+1;
                    while (c<n*m)
                    {
                        if(map[c/m][c%m]==0)
                        {
                            map[c/m][c%m] =1;
                            int r = solve(map);
                            result = max(result, r);
                            map[c/m][c%m] =0;
                        }
                        c++;
                    }
                    
                    map[b/m][b%m] =0;
                }
                b++;
            }
            map[a/m][a%m] =0;
        }
        a++;
    }
    
    
    cout<<result<<endl;
    return 0;
}

나는 벽을 만드는 부분을 while을 3개를 써서 좀 코드가 복잡해 보인다. 

다른 사람의 코드를 보니 벽을 만드는 부분 또한 BFS로 적용하여 푼 코드가 보인다.

그렇게 풀었을 때 좀 더 코드가 간결해 보이게 구현할 수 있다.