BOJ: 14502번 - 연구소 (feat. C++)

백준 14502번 연구소를 풀어보았다. 시뮬레이션을 곁들인 백트래킹, BFS, DFS 문제인데 감만 잡으면 굉장히 쉬운 문제였다. 감을 못잡아서 문제지

솔루션 설계

시뮬레이션 문제라고 느낀 이유는 문제가 시키는 대로 하면 해결의 실마리가 보이기 때문이다. 해결 방법을 크게 생각해보면 다음과 같다.

1. 추가적인 벽 3개를 세운다.
2. 바이러스를 확산 시킨다.
3. 안전 영역 개수를 센다.

1. 추가적인 벽 3개 세우기

벽을 어찌 세워야하나 고민이 됐는데 뾰족한 수가 한 번에 안 오는건 무식하게 다 찾는게 상책이다 효율은 개나 주고 무식하게라도 답을 찾는게 천 번 낫다.

즉, 백트래킹으로 모든 경우의 수를 고려해준다. 빈 칸 중 세 곳을 순서, 중복 모두 없이 고르면 된다. 솔직히 백트래킹 연습이 부족해서 좀 헷갈렸다. N과 M 문제 많이 풀자

void buildWall(int len, int prevPicked) {
    if (len == 3) {
        spreadVirus();
        return;
    }
    
    for (int next = prevPicked + 1; next < emptyLoc.size(); next++) {
        picked[len] = emptyLoc[next];
        buildWall(len + 1, next);
    }
}

2. 바이러스 확산 시키기

BFS 이용해서 바이러스를 사방으로 확산시켜준다.

이 문제에서는 해당 칸을 방문했는지 여부를 기록하는 추가적인 저장공간이 필요하지 않다.

바이러스가 있는 칸과 인접해있으며 값이 0인 칸이 아직 방문하지 않은 칸이기 때문이다.

void spreadVirus() {
    int tmp[10][10];
    queue<pair<int, int>> q;
    int count = safeAreaCount - 3;
    
    // board 복사하면서 바이러스 있는 곳 위치 큐에 삽입
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tmp[i][j] = board[i][j];
            if (tmp[i][j] == 2) {
                q.push({i, j});
            }
        }
    }
    
    // 벽 세우기
    for (int i = 0; i < 3; i++)
        tmp[picked[i].X][picked[i].Y] = 1;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        
        // 북, 동, 남, 서 확인
        for (int dir = 0; dir < 4; dir++) {
            pair<int, int> next = {cur.X + dx[dir], cur.Y + dy[dir]};
            if (checkBounds(next.X, next.Y) && tmp[next.X][next.Y] == 0) {
                q.push(next);
                tmp[next.X][next.Y] = 2;
                count -= 1;
            }
        }
    }
    
    // 안전 영역 개수 삽입
    safeAreaCounts.push_back(count);
}

3. 안전 영역 개수 세기

안전 영역 개수는 따로 for-loop 돌면서 세기 싫어서 꼼수를 부렸다.

(아무것도 안 했을 때 빈 칸 개수) - (추가적인 벽 3개) - (BFS로 바이러스 확산시킬 때마다 1씩 빼기)

이런식으로 구했다. 좀 지저분한 것 같긴하다...

그래서 2021.09.23에 코드 수정했음.

결과

8ms로 통과하신 분들 많더라...

쓸데 없이 모든 시나리오의 안전 영역 개수를 벡터에 넣고 sorting 하는 부분멍청짓을 없앴더니 확실히 시간이 줄었다.

전체 코드 (수정 후)

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

#define X first
#define Y second

typedef pair<int, int> pos_t;

// 북, 동, 남, 서
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

int n, m;
int board[10][10];
vector<pos_t> emptyPos;
pos_t picked[3]; // 추가적으로 벽을 세울 위치 3개
int curMax;

bool checkBounds(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m)
        return false;
    return true;
}

void spreadVirus() {
    int tmp[10][10]; // 추가적인 벽을 세우는 시나리오가 여러 개이므로 board를 복사해서 변경
    queue<pos_t> q; // 바이러스가 있는 위치를 담을 큐
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tmp[i][j] = board[i][j];
            if (tmp[i][j] == 2)
                q.push({i, j});
            else if (tmp[i][j] == 0)
                count += 1;
        }
    }
    
    // 추가적인 벽 3개 세우기
    for (int i = 0; i < 3; i++) {
        tmp[picked[i].X][picked[i].Y] = 1;
    }
    
    count -= 3;
    
    while (!q.empty()) {
        pos_t cur = q.front();
        q.pop();
        
        // 현재 위치를 기준으로 사방을 살펴서 빈 칸일 경우 바이러스 확산
        for (int dir = 0; dir < 4; dir++) {
            pos_t next = {cur.X + dx[dir], cur.Y + dy[dir]};
            
            if (checkBounds(next.X, next.Y) && tmp[next.X][next.Y] == 0) {
                q.push(next);
                tmp[next.X][next.Y] = 2;
                count -= 1;
            }
        }
    }
    curMax = max(curMax, count);
}

void buildWall(int len, int prevPicked) {
    if (len == 3) {
        spreadVirus();
        return;
    }
    
    // prevPicked+1부터 emptyPos.size()-1까지 남은 원소 한 번씩 선택
    for (int next = prevPicked + 1; next < emptyPos.size(); next++) {
        picked[len] = emptyPos[next];
        buildWall(len + 1, next);
    }
}


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 >> board[i][j];
            if (board[i][j] == 0)
                emptyPos.push_back({i, j}); // (i, j)가 빈 칸일 경우 위치 확보
        }
    }
    curMax = 0;
    buildWall(0, -1);
    cout << curMax << '\n';
    return 0;
}

전체 코드 (수정 전)

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

#define X first
#define Y second

// 북, 동, 남, 서
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

int n, m;
int board[10][10];
vector<pair<int, int>> emptyLoc; // 빈 칸의 위치 기록
pair<int, int> picked[3]; // 새롭게 벽을 세울 위치
int safeAreaCount;
vector<int> safeAreaCounts; // 각 경우의 수의 안전 영역 크기 저장


bool checkBounds(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m)
        return false;
    return true;
}

void spreadVirus() {
    int tmp[10][10];
    queue<pair<int, int>> q;
    int count = safeAreaCount - 3;
    
    // board 복사하면서 바이러스 있는 곳 위치 큐에 삽입
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tmp[i][j] = board[i][j];
            if (tmp[i][j] == 2) {
                q.push({i, j});
            }
        }
    }
    
    // 벽 세우기
    for (int i = 0; i < 3; i++)
        tmp[picked[i].X][picked[i].Y] = 1;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        
        // 북, 동, 남, 서 확인
        for (int dir = 0; dir < 4; dir++) {
            pair<int, int> next = {cur.X + dx[dir], cur.Y + dy[dir]};
            if (checkBounds(next.X, next.Y) && tmp[next.X][next.Y] == 0) {
                q.push(next);
                tmp[next.X][next.Y] = 2;
                count -= 1;
            }
        }
    }
    
    // 안전 영역 개수 삽입
    safeAreaCounts.push_back(count);
}

void buildWall(int len, int prevPicked) {
    if (len == 3) {
        spreadVirus();
        return;
    }
    
    for (int next = prevPicked + 1; next < emptyLoc.size(); next++) {
        picked[len] = emptyLoc[next];
        buildWall(len + 1, next);
    }
}

void solution() {
    buildWall(0, -1);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    safeAreaCount = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
            if (board[i][j] == 0) {
                emptyLoc.push_back({i, j});
                safeAreaCount += 1;
            }
        }
    }
    solution();
    sort(safeAreaCounts.begin(), safeAreaCounts.end());
    cout << safeAreaCounts.back() << '\n';
    return 0;
}