[BOJ알고리즘, C++]#14502_연구소, 백트래킹, DFS, BFS

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 백트래킹

[알고리즘]#6_백 트래킹

백트래킹은 문제 해결을 위해 점진적으로 후보 해결책들을 탐색하며, 현재 선택한 경로가 문제 해결로 이어질 수 없다고 판단되면, 이전 단계로 돌아가 다른 후보 경로들에 대한 탐색을 진행합니다. 

 

2. DFS, BFS

[자료구조]#6_그래프

DFS: DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로 시작 노드로부터 더 이상 확장 불가능한 단말 노드에 이르기까지 깊이 우선적으로 탐색하는 방법입니다. 일반적으로, DFS는 재귀 호출 혹은 스택 자료구조를 활용하여 구현합니다.

BFS: BFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로 현재 노드와 인접한 정점들을 우선적으로 탐색하는 방법입니다. 일반적으로, BFS는 큐 자료구조를 활용해 구현 가능합니다.

 

#3. 백트래킹으로 벽 세우고, BFS로 바이러스 퍼뜨리고, 'O' 개수 세기!

1. 먼저, 빈 칸에 대하여 총 3개의 벽을 세우는 모든 경우의 수를 '백 트래킹'을 통해 구합니다.
2. 그리고, 총 3개의 벽을 세웠을 때 BFS를 통해 '2' 주변으로 바이러스를 퍼뜨립니다.
3. 마지막으로, 그래프의 '0' 개수를 세주어, 그 최대 값을 업데이트합니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/14502
*   @문제: 0은 빈 칸, 1은 벽, 2는 바이러스 일때, 3개의 벽을 세워 바이러스가 퍼지지 않은 안전 영역의 크기의 최댓값 구하기
*   @설명
        1. 백트래킹: 0 -> 1로 변경하여, 3개의 벽을 세우는 모든 경우의 수
        2. BFS: 2가 전파되어 최종적으로 안전 영역 최대 값 찾기
*/

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

#define MAX 8
typedef pair<int, int> p;

int N, M, res;
vector<vector<int>> graph(MAX, vector<int>(MAX));
int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};

void bfs(vector<vector<int>>& tempGraph, vector<vector<bool>>& visited)
{
    queue<p> q;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (tempGraph[i][j] == 2)
            {
                q.push({i, j});
                visited[i][j] = true;
            }
        }
    }

    while (!q.empty())
    {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx] || tempGraph[ny][nx] != 0)
                continue;

            visited[ny][nx] = true;
            tempGraph[ny][nx] = 2; // 바이러스 퍼짐
            q.push({ny, nx});
        }
    }
}

void calculateSafeArea()
{
    vector<vector<int>> tempGraph = graph;
    vector<vector<bool>> visited(N, vector<bool>(M, false));

    bfs(tempGraph, visited);

    int safeArea = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (tempGraph[i][j] == 0)
                ++safeArea;
        }
    }
    res = max(res, safeArea);
}

void dfs(int cnt)
{
    if (cnt == 3)
    {
        calculateSafeArea();
        return;
    }

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> graph[i][j];
        }
    }

    dfs(0);

    cout << res << "\n";

    return 0;
}