[BOJ 14502 // C++] 연구소

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14502번 문제인 연구소이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14502

14502번: 연구소

문제에서 요구하는 조건인 "벽 3개 놓기"를 프로그래밍하는 것은 어려워보인다.

 

다행히 연구소의 가로 세로 범위가 작으므로, 이 문제에서는 벽 3개를 놓는 모든 경우의 수를 탐색해도 시간제한 내로 통과할 수 있을 것으로 보인다.

 

따라서 이 문제를 풀기 위해 고안한 알고리즘은 다음과 같다.

 

1) 문제에서 주어진 그래프를 읽어온다. 이 때, 빈 칸 좌표를 담은 벡터 blank와 바이러스 좌표를 담은 큐 originalque를 만든다.

 

2) 벡터 blank에서 세 원소를 고르는 순열(permutation)을 탐색한다. 이는 백트래킹을 이용하여 쉽게 구현할 수 있다. 여기서 고른 세 원소는 새로 벽을 세울 세 곳이다.

 

3) 2에서 구한 세 곳에 벽을 추가한 연구소에서 originalque를 복사한 que를 시작점으로 bfs를 진행한다. 그 뒤, 연구소 범위 안에 남아있는 0의 개수를 세어 기존 답 후보와 비교한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::queue;
using std::vector;

int ans = 0;
int row, column;

struct point {
    int row, column;
};

int originallab[8][8];
int lab[8][8];
bool labvisited[8][8];
queue<point> originalque;
queue<point> que;

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void bfs(vector<point> wall) { // 3개의 세울 벽 좌표를 담고 있는 벡터 wall

    for (int r = 0;r < row;r++) { // lab과 labvisited 초기화 (입력에서 주어진 것과 동일)
        for (int c = 0;c < column;c++) {
            lab[r][c] = originallab[r][c];
            labvisited[r][c] = false;
        }
    }

    que = originalque; // que 초기화 (입력에서 주어진 것과 동일)
    
    vector<point>::iterator iter = wall.begin(); // 벡터 wall에 있는 좌표에 벽을 세운다
    for (iter;iter != wall.end();iter++) {
        point p = *iter;
        lab[p.row][p.column] = 1;
    }
    
    while (!que.empty()) { // BFS로 바이러스를 퍼뜨린다
        point current = que.front(); que.pop();
        int r = current.row;
        int c = current.column;
        for (int i = 0;i < 4;i++) {
            int rr = r + dr[i];
            int cc = c + dc[i];
            if (0 <= rr and rr < row and 0 <= cc and cc < column) {
                if ((!labvisited[rr][cc]) and (lab[rr][cc] == 0)) {
                    labvisited[rr][cc] = true;
                    lab[rr][cc] = 2;
                    point p; p.row = rr; p.column = cc;
                    que.push(p);
                }
            }
        }
    }

    int cnt = 0; // 연구소에 있는 0의 개수를 센다
    for (int r = 0;r < row;r++) {
        for (int c = 0;c < column;c++) {
            if (lab[r][c] == 0) cnt++;
        }
    }

    if (cnt > ans) ans = cnt;
}

vector<point> blank;
vector<point> chosenwall;
void backtracking(int N) {
    if (chosenwall.size() == 3) {//고른 좌표가 3개이면 이 경우에 대해 조사
        bfs(chosenwall);
    }
    else {//고른 좌표가 3개가 아니면 좌표를 추가
        vector<point>::iterator iter = blank.begin();
        for (int i = 0;i < N;i++) {
            iter++;
        }
        for (iter;iter != blank.end();iter++) {
            chosenwall.push_back(*iter);
            backtracking(N + 1);
            chosenwall.pop_back();
            N++;
        }
    }
}

int main()
{
    cin >> row >> column;
    for (int r = 0;r < row;r++) {
        for (int c = 0;c < column;c++) {
            int x; cin >> x;
            originallab[r][c] = x;
            if (x == 0) {
                point p; p.row = r; p.column = c;
                blank.push_back(p);
            }
            if (x == 2) {
                point p; p.row = r; p.column = c;
                originalque.push(p);
            }
        }
    }

    backtracking(0);

    cout << ans;

    return 0;
}