[C/C++] BOJ 3/2 코딩테스트 대비 모의고사 B번 - Baaaaaaaaaduk2 (Easy)

BOJ 3/2 코딩테스트 대비 모의고사 B번 - Baaaaaaaaaduk2 (Easy)

나의 풀이

바둑판의 값이 0인 것들의 위치를 순차적으로 벡터 v에 저장한다.

벡터를 돌면서 0의 위치의 값을 1로 바꾸고 2개가 바뀌었을 때, 죽일 수 있는 상대 돌의 개수를 센다.

bfs방식으로 바둑판의 값이 2인 곳의 탐색을 시작하면서 상하좌우에 2가 있으면 죽일 수 있는 돌의 개수를 1 증가시킨다.

상하좌우에 0이 있으면 탐색을 마쳤을 때, 죽일 수 있는 돌의 개수를 갱신하지 않는다.

모든 탐색을 마친 후, 이전 ans와 비교하여 죽일 수 있는 돌의 개수가 더 많을 때 갱신한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_problemB/BOJ_problemB.cpp

// BOJ 3/2 코딩테스트 대비 모의고사 B번 - Baaaaaaaaaduk2 (Easy)
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
 
int N, M, ans;
int board[21][21];
int visited[21][21];
vector<pair<int, int>>v;
queue<pair<int, int>>q;
 
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0,0,-1,1 };
 
// 죽일 수 있는 상대 돌의 개수 세기
int bfs(int _x, int _y)
{
    int val = 0;
    bool flag = true;
 
    q.push(make_pair(_x, _y));
    visited[_x][_y] = 1;
    val++;
 
    while (!q.empty())
    {
        int qsz = q.size();
        while (qsz--)
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                int mx = x + dx[i];
                int my = y + dy[i];
 
                if (mx < 0 || mx >= N || my < 0 || my >= M) continue;
                if (board[mx][my] == 1) continue;
                if (visited[mx][my]) continue;
                if (board[mx][my] == 0) flag = false;
                if (board[mx][my] == 2)
                {
                    visited[mx][my] = 1;
                    q.push(make_pair(mx, my));
                    val++;
                }
            }
        }
    }
    // 
    if (!flag) val = 0;
    return val;
}
 
void stone(int idx, int cnt)
{
    // 돌을 두개 놓았으면 잡을 수 있는 돌을 체크한다.
    if (cnt == 2)
    {
        int val = 0;
        int lans = 0;
        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (board[i][j] == 2 && visited[i][j] == 0) {
                    val = bfs(i, j);
                    lans += val;
                }
            }
        }
        if (ans < lans) ans = lans;
        return;
    }
 
    int sz = (int)v.size();
    for (int i = idx; i < sz; i++)
    {
        int x = v[i].first;
        int y = v[i].second;
        board[x][y] = 1;
        stone(i + 1, cnt+1);
        board[x][y] = 0;
    }
}
int main(void)
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 0) v.push_back(make_pair(i, j));
        }
    }
 
    int sz = (int)v.size();
    for (int i = 0; i < sz-1; i++)
    {
        int x = v[i].first;
        int y = v[i].second;
        board[x][y] = 1;
        stone(i + 1, 1);
        board[x][y] = 0;
    }
 
    cout << ans;
    return 0;
}