[14502번] 연구소

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

이 문제는 보통 재귀로 푸는데 재귀가 아닌 3중 for문으로 해결 할 수 있다.

자세한 내용은 주석을 통해 달아두었다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <queue>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int n, m, idx;
pii map[102];
vector<pii> virus;
 
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };
 
int bfs(int tmp[][10])
{
    // 내가 받은 배열을 arr에 복사해준다.
    int arr[10][10];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            arr[i][j] = tmp[i][j];
 
    bool visit[10][10] = { false, };
    queue<pii> q;
 
    // 바이러스를 먼저 queue에 넣어 바이러스가 퍼지도록 한다.
    for (int i = 0; i < virus.size(); i++)
        q.push({ virus[i] });
 
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
 
        q.pop();
 
        if (visit[y][x])
            continue;
 
        visit[y][x] = true;
        arr[y][x] = 2;
 
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if ((0 <= ny && ny < n) && (0 <= nx && nx < m) && arr[ny][nx] == 0)
                q.push({ ny,nx });
        }
    }
 
    // 바이러스가 퍼지고 0인 부분을 관찰한다.
    int safe = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!arr[i][j])
                safe++;
 
    return safe;
}
int main()
{
    int arr[10][10];
    memset(arr, 0, sizeof(arr));
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &arr[i][j]);
            map[idx++] = { i,j }; // 각 좌표를 인덱스 번호로 생각해본다.
            // (0,0)은 0번, (0,1)은 1번 ... 
 
            // 바이러스는 벡터에 담아준다.
            if (arr[i][j] == 2)
                virus.push_back({ i,j });
        }
 
    int ans = 0;
    // 세 점을 뽑는다
    for (int c1 = 0; c1 < idx - 2; c1++)
        for (int c2 = c1 + 1; c2 < idx - 1; c2++)
            for (int c3 = c2 + 1; c3 < idx; c3++)
            {
                int y1 = map[c1].first, x1 = map[c1].second;
                int y2 = map[c2].first, x2 = map[c2].second;
                int y3 = map[c3].first, x3 = map[c3].second;
                // 세 점이 모두 0이라면
                if (!arr[y1][x1] && !arr[y2][x2] && !arr[y3][x3])
                {
                    // 막대기로 변환시키고
                    arr[y1][x1] = arr[y2][x2] = arr[y3][x3] = 1;
 
                    // bfs를 돌려 0의 개수를 리턴받는다.
                    int ret = bfs(arr);
 
                    ans = max(ans, ret);
 
                    // 다시 0으로 만든다.
                    arr[y1][x1] = arr[y2][x2] = arr[y3][x3] = 0;
                }
            }
 
    printf("%d", ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>