[BaekJoon/백준] 14502번 연구소

N, M의 최대 범위는 8이며

제한시간은 2초...

 

설마 모든 경우를 다 해봐야만 하는 문제일까 길게 고민하다가,

검색을 통해 풀이 방향을 찾아보았는데

 

역시나 였다..

 

브루트 포스 + DFS를 섞어 쓰는 문제였다.

 

 

3중 for문을 통해 벽을 세울 위치 세 곳을 완전탐색 한 뒤에

DFS를 통해 계산해 나간다...

 

 

다시는 만나지 말자 우리..

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N, M;
int ARR[8][8];
int ARRB[8][8];
bool visit[8][8];


int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, -1, 1};


int MAX, tm;

void dfs(int x, int y) {
    
    int xx, yy;
    
    ARRB[x][y] = 2;
    visit[x][y] = true;
    
    for(int i = 0; i < 4; i++) {
        
        xx = x + mx[i];
        yy = y + my[i];
        
        
        if(xx < 0 || xx >= N || yy < 0 || yy >= M)
            continue;
        
        if(ARRB[xx][yy] == 0 && !visit[xx][yy])
            dfs(xx, yy);
        
    }
    
    
}

int count_zero() {
    
    int C = 0;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(ARRB[i][j] == 0)
                C++;
        }
    }
    
    return C;
}


int main() {
    
    cin >> N >> M;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> ARR[i][j];
        }
    }
    
    
    
    for(int i = 0; i < N * M; i++) {
        
        if(ARR[i / M][i % M] == 0) {
            
            for(int j = i + 1; j < N * M; j++) {
                
                if(ARR[j / M][j % M] == 0) {
                    
                    for(int k = j + 1; k < N * M; k++) {
                        
                        if(ARR[k / M][k % M] == 0) {
                            
                            ARR[i / M][i % M] = 1;
                            ARR[j / M][j % M] = 1;
                            ARR[k / M][k % M] = 1;
                            
                            // 이 복사를 &ARR[0][0] + N*M 하니까 복사가 이상하게 되었었다. 그냥 전체 배열 크기만큼 복사로 바꿨다.
                            copy(&ARR[0][0], &ARR[0][0]+(64), &ARRB[0][0]);
                            memset(&visit, 0, sizeof(visit));
                            
                            for(int q = 0; q < N; q++){
                                for(int w = 0; w < M; w++) {
                                    if(ARRB[q][w] == 2 && !visit[q][w])
                                        dfs(q, w);
                                }
                            }
                            tm = count_zero();
                            
                            if(MAX < tm)
                                MAX = tm;

                            
                            ARR[i / M][i % M] = 0;
                            ARR[j / M][j % M] = 0;
                            ARR[k / M][k % M] = 0;
                        }
                    }
                }
            }
        }
    }
    cout << MAX << "\n";
    
}

 

---

다시 풀었다.

 

M = 8이기에 완전탐색으로 푸는 문제임을 알 수 있었다.

#include <iostream>
#include <cstring>

using namespace std;

int MAP[8][8];
int N, M;


bool VISIT[8][8];
int SAFE_AREA = 0;

int MAX_SAFE_AREA = 0;

int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, 1, -1};

void run_virus_dfs(int x, int y) {
    
    VISIT[x][y] = true;
    
    for(int i = 0; i < 4; i++) {
        
        int xx = x + mx[i];
        int yy = y + my[i];
        
        if(xx < 0 || xx >= N || yy < 0 || yy >= M)
            continue;
        
        if(MAP[xx][yy] == 0 && !VISIT[xx][yy])
            run_virus_dfs(xx, yy);
    }
}

// 바이러스 동작 시뮬레이션
int run_virus() {
    
    
    memset(VISIT, 0, sizeof(VISIT));
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            if(!VISIT[i][j] && MAP[i][j] == 2)
                run_virus_dfs(i, j);
            
        }
    }
    
    SAFE_AREA = 0;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            if(!VISIT[i][j] && MAP[i][j] == 0)
                SAFE_AREA++;
        }
    }

    return SAFE_AREA; // 안전지대
}

// 벽 세우기
// start는 위치, count는 갯수
void dfs(int start, int count) {
    
    if(count == 3) {
        
        // 벽을 세개 다 세웠따
        
        
        int s = run_virus();
        
        if(MAX_SAFE_AREA < s)
            MAX_SAFE_AREA = s;
        
        return;
        
    }
    
    
    for(int i = start; i < N * M; i++) {
            
        
        int x = i / M;
        int y = i % M;
        
    
        // 벽을 세울 수 있다.
        if(MAP[x][y] == 0) {
            
            MAP[x][y] = 1;
            
            dfs(i + 1, count + 1);
            
            MAP[x][y] = 0;
            
        }
        
    }
    
    
}


int main() {
    
    cin >> N >> M;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            cin >> MAP[i][j];
        }
    }
    
    
    dfs(0, 0);
    
    
    
    cout << MAX_SAFE_AREA << "\n";
    
    
}

 

started at 15:39

stopped at 16:05 -> 예제입력 2가 자꾸 6이 나왔다

restarted at 21:30

ended at 21:44 -> i / N이 아니라 i / M

 

---

다시 풀었다.

예전에는 3중 포문도 했었네.. 그리고 두번째 풀이는 지금이랑 비슷한 것 같다.

알아가야 할 점은 

1. memset 사용법

2. dfs 돌면서 조합 구하는 방법

#include <iostream>
#include <vector>
#include <queue>
#define max(a, b) ((a >= b) ? a : b)
using namespace std;

int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};

int N, M;
int virusSize;
int blankSize;

int area[8][8];
bool visited[8][8];

int maxSafeArea = 0;

vector<pair<int, int>> virus;
vector<pair<int, int>> blank;

void spreadVirus() {
    memset(visited, 0, sizeof(visited));
    
    int copyArea[8][8];
    memcpy(copyArea, area, sizeof(area));
        
    queue<pair<int, int>> que;
    for(int i = 0; i < virusSize; i++) {
        que.push({virus[i].first, virus[i].second});
        visited[virus[i].first][virus[i].second] = true;
    }
    
    while(!que.empty()) {
        
        auto top = que.front();
        
        int x = top.first;
        int y = top.second;
        
        que.pop();
        
        for(int i = 0; i < 4 ; i++) {
            int tx = x + mx[i];
            int ty = y + my[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M) continue;
            
            if(copyArea[tx][ty] == 0 && !visited[tx][ty]) {
                que.push({tx, ty});
                copyArea[tx][ty] = 2;
                visited[tx][ty] = true;
            }
        }
    }
    
    int safeArea = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(copyArea[i][j] == 0)
                safeArea++;
        }
    }
    
    maxSafeArea = max(maxSafeArea, safeArea);
}

void buildWallDFS(int index, int count, vector<pair<int, int>>& blank) {
    
    if(count == 3) {
        spreadVirus();
        return;
    }
    
    for(int i = index; i < blankSize; i++) {
        area[blank[i].first][blank[i].second] = 1;
        buildWallDFS(i + 1, count + 1, blank);
        area[blank[i].first][blank[i].second] = 0;
    }
}

int main() {
    
    cin >> N >> M;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> area[i][j];
            
            if(area[i][j] == 2)
                virus.push_back({i, j});
            else if(area[i][j] == 0)
                blank.push_back({i, j});
        }
    }
    
    blankSize = blank.size();
    virusSize = virus.size();
    
    buildWallDFS(0, 0, blank);
    
    cout << maxSafeArea << "\n";
}