BOJ 14502: 연구소

✔ 문제 링크

BOJ 14502: 연구소

---

✔ 문제해결전략

• Brute Force + BFS

---

✔ 해결과정

1) 벽을 세우고 2) 바이러스가 퍼지고 3) 바이러스가 퍼지지 않은 영역의 넓이를 구하면 된다.
벽만 세우고 나면 BFS인데 벽 세우는 것을 어떻게 구현할 것인지가 관건이다.

설마 완전탐색이겠어 했는데 MAP이 MAX 8X8이고 BFS의 시간 복잡도가 O(NM)이므로 3중 for 문으로 벽 3개 세우고 안전 영역까지 구하면 0((NxM)^4)이다. (8x8)^4 = 16,777,216이므로 시간제한 안에 해결할 수 있다.

---

✔ 정답 CODE

#include <bits/stdc++.h>
using namespace std;
int mapp[10][10];
int copiedMap[10][10];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1}; 
int n, m;

// for spreading virus & counting safe area
int bfs() {
    queue<pair<int, int>> q;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            copiedMap[i][j] = mapp[i][j];
            if(mapp[i][j]==2) q.push({i,j}); // virus
        }
    }

    while(!q.empty()) {
        pair<int, int> front = q.front(); q.pop();
        for(int i=0;i<4;i++) {
            int nx = front.first + dx[i];
            int ny = front.second + dy[i];
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            if(copiedMap[nx][ny]==0) {
                copiedMap[nx][ny] = 2;
                q.push({nx,ny});
            }
        }
    }

    int cnt = 0; // counting safe area
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(copiedMap[i][j]==0) cnt++;
        }
    }

    return cnt;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    int maxArea = 0;

    for(int x1=0;x1<n;x1++) {
        for(int y1=0;y1<m;y1++) {
            if(mapp[x1][y1]!=0) continue;

            for(int x2=0;x2<n;x2++) {
                for(int y2=0;y2<m;y2++) {
                    if(mapp[x2][y2]!=0) continue;

                    for(int x3=0;x3<n;x3++) {
                        for(int y3=0;y3<m;y3++) {
                            if(mapp[x3][y3]!=0) continue;

                            if(x1==x2 && y1==y2) continue;
                            if(x2==x3 && y2==y3) continue;
                            if(x3==x1 && y3==y1) continue;

                            mapp[x1][y1] = 1;
                            mapp[x2][y2] = 1;
                            mapp[x3][y3] = 1;

                            int safeArea = bfs();
                            maxArea = max(maxArea, safeArea);
                            
                            
                            mapp[x1][y1] = 0;
                            mapp[x2][y2] = 0;
                            mapp[x3][y3] = 0;
                        }
                    }
                    
                }
            }
            
        }  
    }

    cout << maxArea << '\n';

}

---

✔ Comment

맞왜틀 맞왜틀이 아니라 3중 for 문 쓰다 보니 글씨가 잘 안 보여서 증감식에 오타 냈다. 0퍼에서 out 이면 틀렸겠거니 하고 찾았을 텐데 40퍼쯤에서 계속 틀렸다고 나와서 엣지 케이스 구해서 다 넣어봤는데 맞아서 맞왜틀 맞왜틀 난리 쳤다.

출처가 안 적혀있어서 몰랐는데 삼성 SW 역량 테스트 기출이라고 한다. 완전 탐색, BFS/DFS가 많이 나온다고 듣긴 했는데 이런 식인 지는 몰랐다. 앞으로 비슷한 느낌의 문제 보면 "에이 설마 완전탐색이겠어"라는 생각하지 않고 바로 완전 탐색해야겠다.