16988번: Baaaaaaaaaduk2 (Easy) (백준 온라인 저지, C++)

문제 풀이

 

 처음에 문제만 봤을 때는 오래 걸릴 것이라고 생각했는데, 생각보다 조건이 간단해서 금방 풀 수 있는 문제입니다. 브루트 포스 알고리즘을 이용하였습니다.

우선 바둑판에 있는 빈 칸에 2개의 내 바둑돌을 놓을 수 있는 모든 경우의 수를 고려하여 바둑돌을 놓습니다. 그리고 현재 바둑돌을 놓은 판에서 얼마나 바둑돌을 먹을 수 있는지 확인해 주었습니다. (countBlack함수)

바둑판을 탐색하며 검은색 바둑돌이 존재하는 경우, 이 바둑돌이 속한 군집을 check함수로 넘겨줍니다. 여기서 이 그룹이 먹힌다는 것은 이 그룹에 속한 바둑돌의 인접한 지역에 빈 칸이 하나도 없다는 뜻과 동치이므로, 이 조건에 부합한다면 cnt를 증가시켜 주었습니다. 추가 설명을 코드를 참조하시기 바랍니다!

 

 

코드

 

#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
 
int n, m;
int a[21][21];
bool isVisit[21][21];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
int check(int x, int y) {
 
    int cnt = 0;
 
    bool _get = true;
    queue <pair<int,int>> q;
    q.emplace(x, y);
    isVisit[x][y] = true;
    cnt++;
 
    while (!q.empty()) {
        
        int _x = q.front().first;
        int _y = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = _x + dx[i];
            int ny = _y + dy[i];
 
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (a[nx][ny] == 0) _get = false;
            if (a[nx][ny] == 2 && !isVisit[nx][ny]) {
                isVisit[nx][ny] = true;
                q.emplace(nx, ny);
                cnt++;
            }
        }
     }
 
    if (_get) {
        return cnt;
    }
    else {
        return 0;
    }
}
 
int countBlack() {
 
    int cnt = 0;
    memset(isVisit, false, sizeof(isVisit));
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 2 && !isVisit[i][j]) {
                cnt += check(i, j);
            }
        }
    }
 
    return cnt;
}
 
int main() {
 
    int ans = -1;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
 
    for (int i1 = 0; i1 < n; i1++) {
        for (int j1 = 0; j1 < m; j1++) {
            if (a[i1][j1] == 0) {
                a[i1][j1] = 1;
 
                for (int i2 = i1; i2 < n; i2++) {
                    for (int j2 = 0; j2 < m; j2++) {
                        if ((i1 == i2) && (j1 == j2)) continue;
                        if (a[i2][j2] == 0) {
                            a[i2][j2] = 1;
 
                            int cnt = countBlack();
                            if (ans == -1 || cnt > ans) {
                                ans = cnt;
                            }
 
                            a[i2][j2] = 0;
                        }
                    }
                }
                a[i1][j1] = 0;
            }
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

16988번: Baaaaaaaaaduk2 (Easy)