백준 14502번 연구소

문제 링크입니다: https://www.acmicpc.net/problem/14502

브루트 포스와 BFS(Breadth First Search)를 적절히 이용하여 풀어야하는 문제였습니다.

기존 연구소의 빈칸에 벽 세개를 세울 수 있는 모든 경우의 수를 고려해야하기 때문에 조금 까다로운 문제였습니다.

알고리즘은 아래와 같습니다.

1. 연구소의 모든 칸을 확인하면서 빈칸이 있다면 벽을 세운 뒤 해당 칸의 벽은 고정인 상태로 무작위의 두 빈칸에 벽을 설치합니다.

2. 추가한 벽의 개수가 3개가 되면 BFS 함수를 호출해 바이러스를 확산시킨 뒤 빈칸의 개수를 파악합니다.

3. 모든 경우의 수를 계산한 다음 제일 많은 빈칸이 나왔던 경우의 빈칸의 개수를 출력합니다.

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

 

const int MAX = 8;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

 

int N, M;

int lab[MAX][MAX];

int temp[MAX][MAX];

int result;

 

void BFS(void)

{

        int afterSpread[MAX][MAX];

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < M; j++)

                         afterSpread[i][j] = temp[i][j];

 

        queue<pair<int, int>> q; //y, x

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < M; j++)

                         if (afterSpread[i][j] == 2) //바이러스라면

                                 q.push(make_pair(i, j)); //큐에 넣는다

 

        while (!q.empty())

        {

                 int y = q.front().first;

                 int x = q.front().second;

                 q.pop();

 

                 for (int i = 0; i < 4; i++)

                 {

                         int nextY = y + moveDir[i].y;

                         int nextX = x + moveDir[i].x;

 

                         if(0 <= nextY && nextY < N && 0 <= nextX && nextX < M) //범위 내

                                 if (afterSpread[nextY][nextX] == 0) //빈칸이라면

                                 {

                                          afterSpread[nextY][nextX] = 2; //바이러스 감염

                                          q.push(make_pair(nextY, nextX));

                                 }

                 }

        }

 

        int empty = 0;

        //빈칸 세기

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < M; j++)

                         if (afterSpread[i][j] == 0)

                                 empty++;

 

        result = max(result, empty);

}

 

void makeWall(int cnt)

{

        if (cnt == 3) //벽을 세개 만들었으므로

        {

                 BFS();

                 return;

        }

 

        for(int i=0; i<N; i++)

                 for(int j=0; j<M; j++)

                         if (temp[i][j] == 0)

                         {

                                 temp[i][j] = 1; //마찬가지로 해당칸에 새우고

                                 makeWall(cnt + 1);

                                 temp[i][j] = 0; //다시 허문다

                         }

}

 

int main(void)

{

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < M; j++)

                         cin >> lab[i][j];

       

        for(int i=0; i<N; i++)

                 for(int j=0; j<M; j++)

                         if (lab[i][j] == 0) //빈칸 발견 시

                         {

                                 //연구실 상태를 복사한다

                                 for (int k = 0; k < N; k++)

                                          for (int l = 0; l < M; l++)

                                                  temp[k][l] = lab[k][l];

 

                                 temp[i][j] = 1; //해당 칸에 벽을 세운다

                                 makeWall(1); //벽을 세운 상태이므로 cnt = 1

                                 temp[i][j] = 0; //다시 허문다

                         }

 

        cout << result << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~