[백준 14502] 연구소

안녕하세요 우디🍒입니다 .

오늘은 DFS로 푸는 연구소 문제에 대해 설명해 드릴께요.

 

문제

[백준 14502번] 연구소 바로가기

 

문제 설명

✅ KEY POINT

• 벽은 꼭 3개를 세워야 한다. => 가능한 모든 3개의 좌표 조합을 봐야함. DFS

이 문제는 최적화로 한방에 똬 ! 벽을 3개 세워서 최댓값을 바로 뽜 ! 구할 수 있을까요 ?

😁 : 구할 수 없습니다. 따라서 벽 3개를 세울 수 있는 모든 좌표쌍들을 살펴봐야하는데요 ~

더 자세한 설명은 코드와 함께 설명드리겠습니다 !

코드

x
#include <iostream>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <queue>
using namespace std;
​
static int n, m;
int arr[10][10];//입력받을 배열
int tmp[10][10];//안전영역을 구할 임시배열
​
int dfs_num = 0;//dfs level
int answer = 0;//정답 담아줄 공간
​
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
​
void dfs();
void check();
void check_fun(int x, int y);
void ans();
void array_copy(int arr[10][10]);
​
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
    dfs();//dfs 함수 시작
    cout << answer;
}
​
void dfs()
{
    dfs_num++;
    
    if (dfs_num == 3)//벽이 3개까지 세울 수 있으므로 배열안을 다 검토후 벽 세울수 있는 곳 세우고
    {                //바이러스 퍼뜨린 다음, 안전영역을 구해줘서 최종 정답(answer)을 갱신해줌
        for (int a = 0; a < n; a++)
        {
            for (int b = 0; b < m; b++)
            {
                if (arr[a][b] == 0)//벽 세울수 있으면
                {
                    arr[a][b] = 1;//벽 세우고
                    array_copy(arr);//arr배열 tmp배열로 복사
                    check();//바이러스 퍼뜨림
                    ans();//안전영역구함
                    arr[a][b] = 0;//다시 되돌림
                }
            }
        }
        dfs_num--;//벽 3번째로 올 수 있는 벽들 다 세워줬으면 2번째로 세울 벽을 위해 -1시킴.
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (arr[i][j] == 0)
                {
                    arr[i][j] = 1;//빈공간이면 벽세워줌.
                    dfs();
                    arr[i][j] = 0;//다음 차례를 위해 벽 세워준 것 철수
                }
            }
        }
        dfs_num--;
    }
}
​
void check()//바이러스 퍼뜨려줌
{
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            if (tmp[i][j] == 2) 
                check_fun(i, j);//바이러스 퍼진거 check
}
​
void check_fun(int x, int y)//재귀로 현재좌표에서 상하좌우 살피면서 바이러스 퍼뜨림
{
    int xx, yy = 0;
    for (int i = 0; i < 4; i++)
    {
        xx = x + dx[i];
        yy = y + dy[i];
        if (xx != -1 && xx != n && yy != -1 && yy != m)//배열 넘지 않는 선에서
        {
            if (tmp[xx][yy] == 0)
            {
                tmp[xx][yy] = 2;
                check_fun(xx, yy);
            }
        }
    }
}
​
void ans()//바이러스 퍼뜨린 상태에서 안전영역을 구해주고 최종 정답 갱신해줌.
{
    int out = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (tmp[i][j] == 0) out++;
    if (answer < out) answer = out;
}
​
void array_copy(int arr[10][10])//원래 배열 임시 배열에 복사해줌.
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            tmp[i][j] = arr[i][j];
}
​