[C++][백준 BOJ]14502_연구소.

문제 번호

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

14502번: 연구소

 

 

 

알고리즘 분류

 그래프 탐색(BFS, DFS), 브루트포스(전체탐색).

문제 풀이

 그래프 탐색(BFS 혹은 DFS)과 브루트포스(전체 탐색/완전 탐색)를 모두 사용할 줄 알아야 수월한 문제였다.

처음에는 그래프 탐색에 한해서만 생각해보느라 어떤 식으로 탐색을 진행해야 하는지에만 초점을 맞추어 고민했는데 그냥 다 해보아야 한다. 

문제에서 주어진 크기가 별로 크지 않고 모든 경우의 수를 다 고려해보아도 제한시간내에 풀 수 있을 거라는 계산이 되어서 바로 완전 탐색도 같이 생각해보았다.

 

 우선 벽을 놓을 수 있는 모든 가능성에 대해서 완전 탐색을 해보아야 한다.

// 만들 수 있는 모든 벽의 가능성.
void search()
{
    if (cnt == 0)
        return BFS();

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (MAP[i][j] == 0)
            {
                cnt--;
                MAP[i][j] = 1;
                search();
                cnt++;
                MAP[i][j] = 0;
            }
        }
    }
}

( 처음에는 벽을 놓는 규칙 같은 게 존재할 줄 알았다.)

 

 문제에서 벽 3개를 '꼭' 놓아야 한다고 했음으로 벽3개를 '모두' 놓았다면 BFS(DFS도 가능)를 진행한다. 이때 바이러스를 시작으로 BFS를 진행한다. BFS를 진행하면서 바이러스가 지나간 자리는 바이러스(2)로 상태를 바꾸어준다. 이때 완전 탐색과 BFS를 모두 진행해야 하므로 MAP2라는 2차원 배열을 생성하여서 매번 BFS를 실행할 때마다 MAP(문제에서 주어진 지도에 완전탐색을 통하여 3개의 벽을 추가한 지도)의 내용을 그대로 받아와서 완전탐색에는 영향을 끼치지 않도록 하였다.

 

 즉 매번 BFS를 할때마다 문제에서 주어진 지도에 3개의 벽을 추가한 지도를 MAP2로 옮긴 뒤, MAP2로 BFS를 진행하는 것이다. 

void BFS()
{
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            MAP2[i][j] = MAP[i][j];
    

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            // 바이러스 발견시 BFS 시작.
            if (MAP2[i][j] == 2)
            {
                queue<pair<int, int>> q;

                q.push({i, j});
                Visited[i][j] = true;

                while (!q.empty())
                {
                    int curY = q.front().first;
                    int curX = q.front().second;
                    q.pop();

                    for (int next = 0; next < 4; next++)
                    {
                        int NextY = curY + dxy[next][0];
                        int NextX = curX + dxy[next][1];

                        if (!Visited[NextY][NextX] && MAP2[NextY][NextX] == 0)
                        {
                            q.push({NextY, NextX});
                            Visited[NextY][NextX] = true;
                            MAP2[NextY][NextX] = 2;
                        }
                    }
                }
            }
        }
    }

    memset(Visited, false, sizeof(Visited));

    int temp = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (MAP2[i][j] == 0)
                temp++;
        }
    }

    if (temp > ans)
        ans = temp;
}

  BFS가 종료된 후에는 Visited 배열의 초기화를 잊지 말고 진행해야 다음의 BFS에 영향이 없다. 마지막으로 BFS가 끝난 MAP2의 0의 개수를 모두 찾아서 안전 영역의 크기를 구해준다.

 

전체코드

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

#define MAX 10

// MAP은 문제에서 주어진 원본.
int MAP[MAX][MAX];

int MAP2[MAX][MAX];
bool Visited[MAX][MAX] = {false};
int dxy[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int N, M, cnt = 3, ans = 0;

void Insert()
{
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)        
            cin >> MAP[i][j];        
}

void BFS()
{
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            MAP2[i][j] = MAP[i][j];
    

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            // 바이러스 발견시 BFS 시작.
            if (MAP2[i][j] == 2)
            {
                queue<pair<int, int>> q;

                q.push({i, j});
                Visited[i][j] = true;

                while (!q.empty())
                {
                    int curY = q.front().first;
                    int curX = q.front().second;
                    q.pop();

                    for (int next = 0; next < 4; next++)
                    {
                        int NextY = curY + dxy[next][0];
                        int NextX = curX + dxy[next][1];

                        if (!Visited[NextY][NextX] && MAP2[NextY][NextX] == 0)
                        {
                            q.push({NextY, NextX});
                            Visited[NextY][NextX] = true;
                            MAP2[NextY][NextX] = 2;
                        }
                    }
                }
            }
        }
    }

    memset(Visited, false, sizeof(Visited));

    int temp = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (MAP2[i][j] == 0)
                temp++;
        }
    }

    if (temp > ans)
        ans = temp;
}

// 만들 수 있는 모든 벽의 가능성.
void search()
{
    if (cnt == 0)
        return BFS();

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (MAP[i][j] == 0)
            {
                cnt--;
                MAP[i][j] = 1;
                search();
                cnt++;
                MAP[i][j] = 0;
            }
        }
    }
}

int main()
{
    cin >> N >> M;

    memset(MAP, -1, sizeof(MAP));
    memset(MAP2, -1, sizeof(MAP2));

    Insert();
    search();
    cout << ans << '\n';

    return 0;
}

특이사항

 완전 탐색을 생각하는 데는 오랜 시간이 걸리지 않았지만 정작 구현하는데 잔실수가 많아서 오래 걸렸다.

완전 탐색을 진행할때 i와 j의 시작점을 잘못 설정했었고 지도의 초기화를 0으로 잘못하기도 하였다.

그리고 완전탐색을 진행하는 배열을 그대로 BFS에 사용해서 BFS가 끝나고 나면 지도를 잘못 초기화하는 실수도 있었다.

실수를 줄였다면 빨리 해결할 수 있었던 문제였다.