14502 : 연구소 - DFS, deep copy

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

14502번: 연구소

 

문제요약

3개의 벽을 세워 바이러스가 퍼지지 않는 안전영역의 최대 크기 구하기

 

난이도

Gold 4

---

풀이 포인트

• 단계 꼼꼼히

if (nx >= 0 && nx < n && ny >= 0 && ny < m && b[nx][ny] == 0)   // 조건 고침
            polluteDFS(nx, ny);
            
            
if(nx < 0 || nx >=n || ny < 0 || ny >=m || b[nx][ny] > 0) continue;
// 두 코드 차이 분석해보렴..

---

REVIEW

 

골드 문제 첫 정답!

• 원본 필드와 복사한 필드
• 벽 세울 곳 뽑기 (3중 for문)
  • 원본필드 복사하기 (초기화)
  • 세 군대 벽 세우기
  • dfs 돌리기
  • 돌린 후 0 카운트
  • max값 갱신

풀이에 단계적 접근이 필요해서 골드인가? 그렇게 어려운 문제는 아니었던 듯 하다.

다만, 내 코드는 무려 5중 for문이다~ 최대 크기 자체가 8*8 64정도 밖에 안되니 이렇게 풀 수 있었던 것 같다.

 

모범답안에서의 접근이랑 거의 흡사한 풀이인 것 같다.

하지만 최대,최소 범위보고 시간복잡도 어림잡아 보고 시작했다는 것 차이있으니 배우기!

---

CODE

//n,m : [3,8]

#include <bits/stdc++.h>
using namespace std;

// a: 원본 배열 , b: 바꿀 배열, 마지막에 0이 몇 개인지 체크
// 5중 For문이 괜찮으려나..

int n, m, a[9][9], b[9][9], safeSize, zeroCnt;

vector<pair<int, int>> zeroPlace;
vector<pair<int, int>> virusPlace;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

void polluteDFS (int x, int y){

    b[x][y] = 3;

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

        if (nx >= 0 && nx < n && ny >= 0 && ny < m && b[nx][ny] == 0)   // 조건 고침
            polluteDFS(nx, ny);
    }
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> n >> m;

    for(int i = 0 ; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
            b[i][j] = a[i][j];

            if(a[i][j]== 0){
                zeroPlace.push_back({i,j});
            }else if(a[i][j]==2){
                virusPlace.push_back({i, j});
            }
        }
    }

    //벽 세울 곳 3개 뽑기
    for(int i = 0; i < zeroPlace.size()-2; i++){
        for (int j = i+1; j < zeroPlace.size() - 1 ; j++){
            for(int k = j+1; k < zeroPlace.size(); k++){
                
                //cout <<"원래 필드는 "<<'\n';

                zeroCnt = 0;
                //b를 a로 초기화하는 것 필요.
                for(int v = 0; v < n; v++){
                    for(int x = 0; x < m; x++){
                        b[v][x] = a[v][x];
                        //cout << b[v][x] <<" ";
                    }
                    //cout << '\n';
                }

                // 세군대 벽을 세웠어요.
                b[zeroPlace[i].first][zeroPlace[i].second] = 1;
                b[zeroPlace[j].first][zeroPlace[j].second] = 1;
                b[zeroPlace[k].first][zeroPlace[k].second] = 1;

                // cout << "벽을 세울 좌표는 (" << zeroPlace[i].first << "," << zeroPlace[i].second << ")"
                //  << "(" << zeroPlace[j].first <<", " <<zeroPlace[j].second <<") "
                //  << "(" << zeroPlace[k].first <<", " <<zeroPlace[k].second <<") \n";

                    // 바이러스가 오염을 시킬 겁니다.
                    for (int v = 0; v < virusPlace.size(); v++)
                {
                    polluteDFS(virusPlace[v].first, virusPlace[v].second);
                    
                }

                //cout << "오염 후 필드는 " <<'\n';

                // 안전 영역 0을 카운트해줄게요.

                for(int v = 0; v < n; v++){
                    for(int x = 0; x<m; x++){
                        
                        //cout << b[v][x] <<" ";
                        if(b[v][x] == 0) zeroCnt ++;
                    }
                    //cout <<'\n';
                }
                //cout <<'\n';

                safeSize = max(safeSize, zeroCnt);

            }
        }
    }

    cout << safeSize;
    

}

#include <bits/stdc++.h>
using namespace std;
int a[10][10], visited[10][10], n, m, ret;
vector<pair<int, int>> virusList, wallList;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
void dfs(int y, int x)
{
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx] || a[ny][nx] == 1)
            continue;
        visited[ny][nx] = 1;
        dfs(ny, nx);
    }
    return;
}
int solve()
{
    fill(&visited[0][0], &visited[0][0] + 10 * 10, 0);
    for (pair<int, int> b : virusList)
    {
        visited[b.first][b.second] = 1;
        dfs(b.first, b.second);
    }

    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == 0 && !visited[i][j])
                cnt++;
        }
    }
    return cnt;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 2)
                virusList.push_back({i, j});
            if (a[i][j] == 0)
                wallList.push_back({i, j});
        }
    }
    for (int i = 0; i < wallList.size(); i++)
    {
        for (int j = 0; j < i; j++)
        {
            for (int k = 0; k < j; k++)
            {
                a[wallList[i].first][wallList[i].second] = 1;
                a[wallList[j].first][wallList[j].second] = 1;
                a[wallList[k].first][wallList[k].second] = 1;
                ret = max(ret, solve());
                a[wallList[i].first][wallList[i].second] = 0;
                a[wallList[j].first][wallList[j].second] = 0;
                a[wallList[k].first][wallList[k].second] = 0;
            }
        }
    }
    cout << ret << "\n";
    return 0;
}