백준 14502번: 연구소

---

여러가지 고려해야할 점이 많아서 복잡해 보이지만 결국은 조합을 구하는 완전탐색 문제이다.

주어진 배열에서 3개의 0을 1로 바꾸는 모든 경우의 수를 구한다. --> N개의 원소에서 3개를 뽑는 경우의 수와 같음

바뀐 배열에서 2의 상하좌우에 존재하는 0을 2로 바꿔주고, 이 작업을 더이상 바꿀 수 없을 때 까지 반복한 다음 배열에서 0의 갯수를 구하여 가장 큰 값을 결과로 반환해주면 된다.

---

#include <iostream>
#include <cstring>
using namespace std;
 
 
int col, row;
int board[9][9];
bool visited[9][9];
 
int max(int a, int b) { return a > b ? a : b; }
 
int Solution(int startY, int wall)
{
    if (wall == 3)            // 기저사례. 벽을 3개 쌓았다면 2를 다 퍼뜨리고 값을 반환한다.
    {
        int temp[9][9];
        for (int i = 0; i < col; i++)
            for (int j = 0; j < row; j++)
                temp[i][j] = board[i][j];
 
        bool state = false;
        while (state == false)
        {
            state = true;
            for (int i = 0; i < col; i++)
                for (int j = 0; j < row; j++)
                    if (temp[i][j] == 2)
                    {
                        if (i > 0)    // 2 의 9시 방향
                            if (temp[i - 1][j] == 0)
                            {
                                temp[i - 1][j] = 2;
                                state = false;
                            }
                        if (j > 0)    // 2의 12시 방향
                            if (temp[i][j - 1] == 0)
                            {
                                temp[i][j - 1] = 2;
                                state = false;
                            }
                        if (i + 1 < col)    // 2의 6시 방향
                            if (temp[i + 1][j] == 0)
                            {
                                temp[i + 1][j] = 2;
                                state = false;
                            }
                        if (j + 1 < row)    // 2의 3시 방향
                            if (temp[i][j + 1] == 0)
                            {
                                temp[i][j + 1] = 2;
                                state = false;
                            }
                    }
        }
        int cnt = 0;
        for (int i = 0; i < col; i++)
            for (int j = 0; j < row; j++)
                if (temp[i][j] == 0) cnt++;
        return cnt;
    }
 
    int ret = -1;
    for (int i = startY; i < col; i++)
    {
        for (int j = 0; j < row; j++)
        {
            if (board[i][j] == 0)
            {
                if (visited[i][j] == true) continue;
                visited[i][j] = true;
                board[i][j] = 1;
                ret = max(ret, Solution(i, wall + 1));
                board[i][j] = 0;
                visited[i][j] = false;
            }
        }
    }
    return ret;
}
 
int main(void)
{
    cin >> col >> row;
    memset(visited, false, sizeof(visited));    // 배열 전체를 방문하지 않은상태로 초기화
    for (int i = 0; i < col; i++)
    {
        for (int j = 0; j < row; j++)
        {
            int n;
            cin >> n;
            board[i][j] = n;
        }
    }
    cout << Solution(0,0) << endl;
 
    return 0;
}

알고리즘 200일 프로젝트 - 6day

다른 사람들이 푼 방식을 보니 바이러스를 확산시키는데 DFS, BFS를 사용했다.

나는 아직 DFS와 BFS에 대해 잘 모르는 상태라 다소 무식하게 풀어낸거 같다.

그 부분들을 공부하게 되면 다시한번 풀어보도록 해야겠다.