백준 16988 - Baaaaaaaaaduk2 (Easy)(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16988

16988번: Baaaaaaaaaduk2 (Easy)

주어진 map에서 흰 돌을 2개 놓을 때, 검은색 돌을 최대한 많이 죽을 수 있는 개수를 구하는 문제입니다.

 

돌을 놓을 수 있는 곳에 모두 놓아본 뒤, 잡을 수 있는 돌의 개수를 전부 확인해보면 됩니다.

 

<문제 해결 과정>

1. 2개의 돌을 차례대로 놓는다.

2. 돌을 놓은 뒤, 검은 색 돌을 몇개를 잡을 수 있는지를 확인해본다.

3. 모든 경우를 확인한 뒤, 최대로 잡은 돌의 개수를 출력한다.

 

먼저 2개의 위치를 차례대로 놓는 방법부터 확인해보겠습니다.

void select_space(int start, int cnt){
    if(cnt == 2){ // 2개의 위치가 선택됐다면
        Copy_map();
        memset(check, 0, sizeof(check));
        copy_map[can_put[selects[0]].F][can_put[selects[0]].S] = 1; // 선택된 위치를 1로 만든다
        copy_map[can_put[selects[1]].F][can_put[selects[1]].S] = 1;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                if(copy_map[i][j] == 2 && check[i][j] == 0) bfs(i, j); 
            }
        }
        max_catch = max(max_catch, full_catch);
        full_catch = 0;
    }
    else{
        for(int i = start; i < can_put.size(); i++){ // 2개의 위치를 선택할 때까지 다음 돌을 선택한다.
            if(Select[i]) continue; // 이전에 선택된 돌이라면 pass
            Select[i]= true; // 해당 위치를 선택했다고 저장한다.
            selects.push_back(i);
            select_space(i, cnt+1);
            selects.pop_back(); 
            Select[i] = false; // 값을 false로 바꿔줌으로 선택을 해제한다.
        }
    }
}

먼저, 2개의 위치를 선택하는 원리에 대해서 생각해보겠습니다.

N개 위치 중에서 2개를 선택만 하면 됩니다.

따라서 (X, Y) , (Y, X)는 같은 선택이 된다는 의미이기도 합니다.

(1, 2) -> (1, N) , (2, 3) -> (2, N) .... (N-1, N)으로 하나씩 바꿔가면서 선택하면 모든 경우를 확인할 수 있습니다.

 

 

위치를 선택을 했으면, BFS or DFS를 통해 탐색을 시작하면 됩니다.

검은색 돌을 몇개를 잡을 수 있는지를 구하는 문제이니

map에서 검은색 돌이 있는 부분을 확인해줍니다.(흰색 돌을 놓는 위치마다 map이 달라지기 때문에 map을 복사해줘야합니다.)

 

검은 색 돌 부분을 찾아서 4방향 탐색을 할 때, 빈 부분을 만나게 된다면 해당 돌은 잡을 수 없다는 의미가 됨으로 

변수 하나를 만들어 false 값을 넣어줍니다. 

탐색이 끝났을 때, 해당 변수가 false를 가지고 있다면 해당 그룹은 못잡는다는 것임으로 pass,

true 값을 가지고 있다면 그룹의 개수를 세준 뒤, 최대 값과 비교합니다.

 

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define F first
#define S second

using namespace std;

int N, M;
int map[21][31];
int copy_map[21][31];
int check[21][31];
bool Select[611];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pair<int, int>> can_put;
vector<int> selects;
int full_catch, max_catch;

void Copy_map(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            copy_map[i][j] = map[i][j];
        }
    }
}

void bfs(int X, int Y){
    bool flag = true;
    int Catch = 1;
    queue<pair<int, int>> q;
    check[X][Y] = 1;
    q.push({X, Y});
    while(!q.empty()){
        int x = q.front().F;
        int y = q.front().S;
        q.pop();
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                if(check[xx][yy] == 1) continue;
                if(copy_map[xx][yy] == 0) {
                    flag = false;
                }
                if(copy_map[xx][yy] == 2){
                    Catch++;
                    q.push({xx, yy});
                    check[xx][yy] = 1;
                }
            }    
        }
    }
    if(flag) full_catch += Catch;
}

void select_space(int start, int cnt){
    if(cnt == 2){
        Copy_map();
        memset(check, 0, sizeof(check));
        copy_map[can_put[selects[0]].F][can_put[selects[0]].S] = 1; // 선택된 위치를 1로 만든다
        copy_map[can_put[selects[1]].F][can_put[selects[1]].S] = 1;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                if(copy_map[i][j] == 2 && check[i][j] == 0) bfs(i, j); 
            }
        }
        max_catch = max(max_catch, full_catch);
        full_catch = 0;
    }
    else{
        for(int i = start; i < can_put.size(); i++){
            if(Select[i]) continue;
            Select[i]= true;
            selects.push_back(i);
            select_space(i, cnt+1);
            selects.pop_back();
            Select[i] = false;
        }
    }
}

void solve(){
    memset(Select, false, sizeof(Select));
    select_space(0, 0);
    cout << max_catch;
}

int main() {
    cin.tie(0);    
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
            if(map[i][j] == 0) can_put.push_back({i, j});
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.