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

www.acmicpc.net/problem/14502

14502번: 연구소

<풀이>

1. 연구소 지도를 입력받는다.

2. 연구소에 벽 3개를 세우고, 바이러스가 퍼졌을 때 안전 영역을 구한다.

3. 안전 영역의 최댓값을 출력한다.

 

<해법>

1. 연구소에 벽 3개를 세우는 방법.

=> 벽 3개를 어떻게 세워야 하는지 정할 수 있는 최적의 방법이 없습니다. 따라서, 가능한 곳에 벽 3개를 모두 세워보아야 합니다. 저는 벽을 세울 수 있는 좌표들을 담아 놓고, 하나씩 세우는 방법으로 진행하였습니다. 기본적인 브루트포스 진행방식을 이해하고 있어야 합니다.

 

2. 안전 영역을 구하는 방법.

=> 벽 3개를 모두 세웠으면 이제 바이러스를 퍼트려야 합니다. 바이러스는 BFS를 이용하여 퍼트렸습니다. 마지막으로, 안전 영역을 구하는 방법은 바이러스가 다 퍼진 후, 남은 영역의 개수를 세는 방식으로 진행하였습니다.

 

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
//구조체 : 좌표
struct pos {
    int x, y;
};
 
//4방향 : 북,동,남,서
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N, M;
int map[10][10];
vector<pos> space;
vector<pos> virus;
int copyMap[10][10];
int answer;
 
void spread_virus_to_copyMap() {
 
    queue<pos> q;
    
    //큐에 바이러스 모두 담기
    for (int i = 0; i < virus.size(); i++) {
        q.push(virus[i]);
    }
 
    //BFS 탐색
    while (!q.empty()) {
        pos cur = q.front();
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            pos nxt = cur;
            nxt.x += di[i];
            nxt.y += dj[i];
 
            if (nxt.x < 0 || nxt.y < 0 || nxt.x >= N || nxt.y >= M) {
                continue;
            }
 
            if (copyMap[nxt.x][nxt.y] == 0) {
                copyMap[nxt.x][nxt.y] = 2;
                q.push(nxt);
            }
        }
    }
}
 
int count_safeSpace_from_copyMap() {
 
    int safeSpaceCnt = 0;
 
    //안전 영역(=0) 개수 세기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (copyMap[i][j] == 0) {
                safeSpaceCnt++;
            }
        }
    }
 
    //안전 영역 반환
    return safeSpaceCnt;
}
 
void makeWall(int spaceIdx, int wallCnt) {
 
    //종료조건 : 벽을 3개 모두 세웠을 경우
    if (wallCnt == 3) {
 
        //시뮬레이션을 하기 위해 맵 복사
        memcpy(copyMap, map, sizeof(copyMap));
 
        //복사된 맵에 바이러스 퍼트리기(BFS)
        spread_virus_to_copyMap();
 
        //안전 영역 구하기
        int safeSpaceCnt = count_safeSpace_from_copyMap();
 
        //결과 갱신
        if (safeSpaceCnt > answer) {
            answer = safeSpaceCnt;
        }
 
        //종료
        return;
    }
 
    //빈 공간에 벽 하나씩 세우기
    for (int i = spaceIdx; i < space.size(); i++) {
        
        /*
        빈 공간 좌표 꺼내서, 벽을 세우고 탐색한 후 다시 벽 없애기
        */
 
        int x = space[i].x;
        int y = space[i].y;
 
        map[x][y] = 1;
        makeWall(i + 1, wallCnt + 1);
        map[x][y] = 0;
    }
}
 
int main() {
 
    //초기화
    answer = -1;
    
    //입력
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
 
            //빈 공간(=벽 세울 위치) 저장
            if (map[i][j] == 0) {
                space.push_back({ i,j });
            }
            //바이러스 위치 저장
            else if (map[i][j] == 2) {
                virus.push_back({ i,j });
            }
        }
    }
 
    //벽 세우기(브루트포스)
    makeWall(0, 0);
 
    //출력
    cout << answer;
 
    //종료
    return 0;
}

 

브루트포스와 BFS에 대해 알아볼 수 있는 문제였습니다.