[BOJ][백준 14502] 연구소 - C++

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

14502번: 연구소

백준 사이트의 14502번 문제, 연구소 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

입력) 가로, 세로, 연구소 상태

• 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
• 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
• 빈 칸의 개수는 3개 이상이다.
• 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
• 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

---

1. 문제풀이 아이디어

• 벽을 반드시 3개 세워야 하는 것이 포인트다.
• 최댓값을 구하는 문제기 때문에 모든 경우를 살펴보기로 하였다.
• 그래서 3개의 벽을 먼저 DFS 알고리즘으로 뽑아주었다.
• 3개의 벽을 뽑은 다음에, BFS 알고리즘을 이용하여 안전 영역을 구해주었다.

---

2. 코드 핵심 부분

1) Map에 벽 3개를 설지하는 DFS 함수,

  조합이니깐 중복을 처리하기 위해 for문으로 DFS를 구성하였다.

  3개를 다 뽑고나서 check함수를 실행하는 것을 확인할 수 있다.

// 벽 3개를 설치하는 함수, 일단 벽 설치부터 한 뒤에,
void dfs(int lv, int sy, int sx) {

    if (lv == 3) {

        int ret = check();
        if (ret > Max)
            Max = ret;

        return;
    }

    for (int i = sy; i < N; i++) {

        if (i == sy) {
            for (int j = sx; j < M; j++) {
                if (arr[i][j] != 0)
                    continue;

                arr[i][j] = 1;
                dfs(lv + 1, i, j);
                arr[i][j] = 0;
            }
        }

        else {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] != 0)
                    continue;

                arr[i][j] = 1;
                dfs(lv + 1, i, j);
                arr[i][j] = 0;
            }
        }

    }
}

 

2) 안전지역을 확인하는 BFS 함수,

  상하좌우 4방향으로 갈 수 있는지를 따져 퍼져나가며 바이러스 체크를 하였다.

  이 BFS작업을 위해 input 시에 바이러스 배열을 따로 만들어서 그 정보를 저장하였다.

// 벽 3개를 전부 설치하고 BFS로 안전지역을 확인한다.
int check() {

    int diry[4] = { -1, 0, 1, 0 };
    int dirx[4] = { 0, -1, 0, 1 };
    int visited[8][8] = { 0 };
    int ans = 0;

    for (int i = 0; i < vCnt; i++) {
        queue<Node> q;
        q.push({ virus[i][0], virus[i][1] });

        while (!q.empty()) {

            Node now = q.front();
            q.pop();

            for (int j = 0; j < 4; j++) {

                int ny = now.y + diry[j];
                int nx = now.x + dirx[j];

                if (ny < 0 || nx < 0 || ny >= N || nx >= M)
                    continue;

                if (visited[ny][nx] == 1)
                    continue;
                if (arr[ny][nx] != 0)
                    continue;

                visited[ny][nx] = 1;
                ans++;
                q.push({ ny,nx });

            }
        }

    }

    // 나는 바이러스 퍼진거만 세서 이렇게 복잡해졌다.
    // 전체 - 벽 - 3개설치한벽 - 바이러스 퍼진거 - 바이러스 원래수
    int num = N * M - wCnt - 3 - ans - vCnt;
    return num;
}

---

3. 전체 코드

#include <iostream>
#include <queue>

using namespace std;

struct Node {
    int y;
    int x;
};

// 필요 인자들
int Max = 0;
int N, M;
int arr[8][8];
int virus[10][2];
int vCnt;
int wCnt;

// 인자 입력받는 함수
void input() {

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 2) {
                virus[vCnt][0] = i;
                virus[vCnt][1] = j;
                vCnt++;
            }
            else if (arr[i][j] == 1) {
                wCnt++;
            }
        }
    }

}

// 벽 3개를 전부 설치하고 BFS로 안전지역을 확인한다.
int check() {

    int diry[4] = { -1, 0, 1, 0 };
    int dirx[4] = { 0, -1, 0, 1 };
    int visited[8][8] = { 0 };
    int ans = 0;

    for (int i = 0; i < vCnt; i++) {
        queue<Node> q;
        q.push({ virus[i][0], virus[i][1] });

        while (!q.empty()) {

            Node now = q.front();
            q.pop();

            for (int j = 0; j < 4; j++) {

                int ny = now.y + diry[j];
                int nx = now.x + dirx[j];

                if (ny < 0 || nx < 0 || ny >= N || nx >= M)
                    continue;

                if (visited[ny][nx] == 1)
                    continue;
                if (arr[ny][nx] != 0)
                    continue;

                visited[ny][nx] = 1;
                ans++;
                q.push({ ny,nx });

            }
        }

    }

    // 나는 바이러스 퍼진거만 세서 이렇게 복잡해졌다.
    // 전체 - 벽 - 3개설치한벽 - 바이러스 퍼진거 - 바이러스 원래수
    int num = N * M - wCnt - 3 - ans - vCnt;
    return num;
}

// 벽 3개를 설치하는 함수, 일단 벽 설치부터 한 뒤에,
void dfs(int lv, int sy, int sx) {

    if (lv == 3) {

        int ret = check();
        if (ret > Max)
            Max = ret;

        return;
    }

    for (int i = sy; i < N; i++) {

        if (i == sy) {
            for (int j = sx; j < M; j++) {
                if (arr[i][j] != 0)
                    continue;

                arr[i][j] = 1;
                dfs(lv + 1, i, j);
                arr[i][j] = 0;
            }
        }

        else {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] != 0)
                    continue;

                arr[i][j] = 1;
                dfs(lv + 1, i, j);
                arr[i][j] = 0;
            }
        }

    }
}

int main() {

    // input
    input();

    // solve -> dfs로 벽3개 세우고 그 다음에 안전영역 계산
    dfs(0, 0, 0);

    // output
    cout << Max;

}

---

4. 문제 풀이를 마치며..

본인 풀이의 성능

사실 처음 문제를 보고 발상자체는 쉽게 떠올랐다.

최댓값, 경우의 수, 3개 설치니깐 DFS가 바로 떠올랐다.

 

문제는 DFS로 뽑고 그 안에 BFS를 또 구현해야 하니 실행시간이 약간 걱정이었다.

그래서 최대한 벡터 사용을 자제하고 배열로 문제를 해결하였다.

 

평소보다 주석이 적고 변수 설정이 약간 더러운 감이 있는데,

스터디가 끝나는 바람에 혼자 문제를 풀고 있어서 그렇다..

 

앞으로 이렇게 백준문제를 혼자 푸려고 하는데 블로그 업로드도 병행하고자 한다.

그래야 더 클린코드로 짜려 노력하게 될 것 같아서.