[C++] 백준 16988번 - Baaaaaaaaaduk2 (Easy) (BFS, DFS, 완전 탐색)

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

16988번: Baaaaaaaaaduk2 (Easy)

 

 

 

 

문제

서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 주인 자리에서 쫓겨난지 오래이다. 그나마 다행인 것은 AI가 인간을 적대적으로 대하지 않고, 도리어 AI가 쌓아올린 눈부신 기술의 발전으로 모든 사람이 무제한적인 재화를 사용할 수 있게 되어 한 세기 전의 사람들이 바라던 돈 많은 백수와 같은 삶을 누릴 수 있게 됐다는 사실이다. 대다수의 인간들은 현재의 상황에 만족하고 더 이상 발전을 포기한 채 놀고 먹으면서 시간을 보내고 있지만 일부 인간들은 인류의 영광을 되찾기 위해 저항군을 조직해 AI에게 투쟁하고 있다.

저항군은 AI에게 승산이 있는 종목을 찾고 있다. 이러한 종목을 가지고 AI에게 승부를 걸어 전 인류에게 도전정신과 인간의 위대함을 증명하고 싶기 때문이다. 저항군의 지도부는 무려 12시간에 걸쳐 AI에게 승산이 있는 종목을 찾기 위한 회의를 진행했다. 회의에서 알고리즘 문제 풀이 대결, 가위불바위총번개악마용물공기보스펀지늑대나무사람뱀 게임, 캐치마인드, 알까기, 스타크래프트, 똥 피하기 게임, 딸기 2비트, 딸기수박당근참외메론 게임, 백일장, 사생 대회 등 다양한 아이디어가 나왔지만 단 0.01%라도 승산이 있어 보이는 종목은 하나도 없었다.

그렇게 모두가 낙담하던 중 누군가가 역사책을 뒤져 인간이 AI에게 승산이 있는 종목을 찾아냈다. 바로 정확히 100년 전에 있었던 이세돌과 알파고의 바둑 대결이었다. 물론 알파고는 그 이후로 발전을 거듭했기에 바둑에서의 승산은 없지만 바둑의 룰을 변형한 Baduk2라는 종목에서는 이세돌이 알파고에게 한 세트를 이긴 것과 같이 인간이 AI에게 승산이 있다고 판단했다.

Baduk2의 룰은 바둑과 거의 유사하지만 양 선수가 돌을 1개씩 번갈아 두는 것이 아니라 2개씩 둔다는 점이 다르다. 서술의 편의를 위해 상하좌우로 인접한 같은 색 돌의 집합을 그룹이라고 하자. 아래의 판에서는 흑의 그룹과 백의 그룹이 각각 3개씩 존재한다.

Baduk2에서는 일반적인 바둑과 동일하게 자신의 돌로 상대방의 그룹을 빈틈없이 에워싸면 갇힌 돌을 죽일 수 있다. 어느 그룹이 빈틈없이 에워싸였다는 것은 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것과 동치이다.

그리고 Baduk2에서는 모든 비어있는 칸에 돌을 둘 수 있다. 설령 상대 돌로 둘러싸여 있어 스스로 잡히는 곳이라고 하더라도 상관이 없다. 아래와 같은 상황을 생각해보자.

두 빨간 칸 모두 백의 입장에서 착수할 경우 연결된 그룹이 흑돌로 둘러싸이게 되어 원래 바둑의 규칙에서는 백의 입장에서 스스로 잡히는 곳이지만 Baduk2에서는 이와 무관하게 백이 빨간 칸 두 곳에 착수해 8개의 흑돌이 들어있는 그룹의 돌을 죽일 수 있다.

저항군은 AI에게 Baduk2로 도전장을 내밀었고 AI는 의외로 순순히 도전을 받아들였다. 이제 저항군은 2116년 3월 9일, 인류의 자존심을 건 Baduk2 대결을 시작한다. 그리고 당신에게 인류의 승리를 돕기 위해 현재 판 위에서 돌 2개를 두어 상대 돌을 최대한 많이 죽이게끔 하는 프로그램을 작성하는 임무가 주어졌다. 인류의 명예를 걸고 현재 판이 주어질 때 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 구하는 프로그램을 작성하자.

입력

첫째 줄에 바둑판의 행의 갯수와 열의 갯수를 나타내는 N(3 ≤ N ≤ 20)과 M(3 ≤ M ≤ 20)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 빈 칸, 1은 나의 돌, 2는 상대의 돌을 의미한다. 빈 칸이 2개 이상 존재함과 현재 바둑판에서 양 플레이어 모두 상대방의 돌로 빈틈없이 에워싸인 그룹이 없음이 모두 보장된다.

출력

첫째 줄에 현재 판에서 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 출력한다.

 

 

---

 

접근 방법 

DFS와 두번의 BFS를 활용하면 쉽게 풀 수 있는 문제였다.

 

알고리즘은 크게 아래의 두 단계로 나뉜다. 

1) 빈 칸들 중에서 "내 돌 두개를 놓을 좌표 두개" 를 고르는 모든 경우를 구한다. (DFS)

2) 내 돌 두개를 놓았으면, 그 상태에서 내 돌에 둘러쌓여 죽는 상대 돌의 개수를 구한다. -> 이 개수를 비교해서 최대 값을 구한다.

 

그럼 2)에서 죽게되는 상대 돌의 개수를 어떻게 구할까?

먼저, BFS를 이용해서 상대 돌의 그룹들을 구한다. 각 그룹의 시작 좌표를 "partnerGroup_StartLoc"  벡터에 저장한다. 

그 후, 이 벡터에 저장된 [상대 돌 그룹의 시작 좌표] 에서  한번 더 BFS를 돌린다. BFS는 아래와 같이 동작한다.

 

//어느 그룹이 빈틈없이 에워싸였다는 것 <=> 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것
int getKilled(){
    int ret = 0;

    int v[20][20];
    
    for (int i = 0; i < partnerGroup_StartLoc.size(); i++)
    { //BFS로 흰색 그룹들 모두 검사. 둘러 쌓여있는 그룹에서 죽는 돌 개수 세기 

        queue<pair<int,int>> tmpQue;
        
        memset(v, 0, sizeof(v));
        int r = partnerGroup_StartLoc[i].first;
        int c = partnerGroup_StartLoc[i].second;

        v[r][c] = 1;
        int killedCnt = 1;
        bool isContinue = true;

        tmpQue.push(make_pair(r,c));
        while(!tmpQue.empty()){     

            int cr = tmpQue.front().first;
            int cc = tmpQue.front().second;
            tmpQue.pop();

            for (int k = 0; k < 4; k++)
            {
                int nr = cr + dr[k];
                int nc = cc + dc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M || v[nr][nc]==1) continue;

                //빈칸이랑 인접했으면 그 그룹은 에워쌓이지 않은 것. 
                if(map[nr][nc] == 0){
                    isContinue = false;
                    break;
                }
                //백돌끼리 인접한 것이므로 큐에 담고 계속해서 검사 진행한다.
                if(map[nr][nc] == 2){
                    v[nr][nc] = 1;
                    killedCnt++;
                    tmpQue.push(make_pair(nr,nc));
                }
                    
            }
            if(!isContinue) break;
        }
        if(isContinue){ //모두 둘러 쌓인 경우에만 합해준다. 
            ret += killedCnt;
        }
    }
    return ret;
}

- next좌표가 2이면 v[][]에 방문했음을 표시한다.

- next좌표가 0이면 빈칸이므로 해당 그룹은 내 돌에 의해 둘러 쌓여있지 않은 그룹이므로 패스하고 다음 그룹을 검사한다.

- next좌표가 1이면 큐에 담지 않고 계속해서 큐에 담긴 좌표들 검사를 진행한다.

 

그 그룹이 모두 빈칸이랑 한번도 인접한 적이 없다면 죽은 돌의 개수를 합한다.

모든 그룹을 검사해서 죽은돌의 개수 합을 리턴하며, 리턴된 값들 중 최대값을 구해서 출력하면 된다..

 

 

 

 

전체 코드는 아래와 같다.

 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <string.h>
using namespace std;

int map[20][20];
int visited[20][20];
int N, M;
//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int answer = 0;

vector<pair<int,int>> spaceVec;
vector<pair<int, int>> partnerGroup_StartLoc;
vector<int> pickedIdxVec;

int picked[400] = {0,};

//상대편 돌들의 그룹 표시하기 위한 함수 
void BFS(int r, int c){

    visited[r][c] = 1;
    queue<pair<int,int>> que;
    que.push(make_pair(r,c));

    while(!que.empty()){

        int cr = que.front().first;
        int cc = que.front().second;
        que.pop();

        for(int i = 0; i<4; i++){
            int nr = cr + dr[i];
            int nc = cc + dc[i];

            if(nr<0 || nr>=N || nc<0 || nc>=M || visited[nr][nc] == 1 || map[nr][nc] != 2) continue;

            visited[nr][nc] = 1;
            que.push(make_pair(nr, nc));
        }


    }

}



//어느 그룹이 빈틈없이 에워싸였다는 것 <=> 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것
int getKilled(){
    int ret = 0;

    int v[20][20];
    
    for (int i = 0; i < partnerGroup_StartLoc.size(); i++)
    { //BFS로 흰색 그룹들 모두 검사. 둘러 쌓여있는 그룹에서 죽는 돌 개수 세기 

        queue<pair<int,int>> tmpQue;
        
        memset(v, 0, sizeof(v));
        int r = partnerGroup_StartLoc[i].first;
        int c = partnerGroup_StartLoc[i].second;

        v[r][c] = 1;
        int killedCnt = 1;
        bool isContinue = true;

        tmpQue.push(make_pair(r,c));
        while(!tmpQue.empty()){     

            int cr = tmpQue.front().first;
            int cc = tmpQue.front().second;
            tmpQue.pop();

            for (int k = 0; k < 4; k++)
            {
                int nr = cr + dr[k];
                int nc = cc + dc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M || v[nr][nc]==1) continue;

                //빈칸이랑 인접했으면 그 그룹은 에워쌓이지 않은 것. 
                if(map[nr][nc] == 0){
                    isContinue = false;
                    break;
                }
                //백돌끼리 인접한 것이므로 큐에 담고 계속해서 검사 진행한다.
                if(map[nr][nc] == 2){
                    v[nr][nc] = 1;
                    killedCnt++;
                    tmpQue.push(make_pair(nr,nc));
                }
                    
            }
            if(!isContinue) break;
        }
        if(isContinue){ //모두 둘러 쌓인 경우에만 합해준다. 
            ret += killedCnt;
        }
    }
    return ret;
}

void pickDFS(int toPick){
    if(toPick==0)
    { //돌 놓을 위치 2개 골랐으면, 그 상태에서 죽일 수 있는 상대 돌의 최대 갯수 구하기
        int r1 = spaceVec[pickedIdxVec[0]].first;
        int c1 = spaceVec[pickedIdxVec[0]].second;

        int r2 = spaceVec[pickedIdxVec[1]].first;
        int c2 = spaceVec[pickedIdxVec[1]].second;

        map[r1][c1] = 1; map[r2][c2] = 1;   //내 돌 놓기
        int sum = getKilled();
        answer = max(answer, sum);
        map[r1][c1] = 0; map[r2][c2] = 0;   //원상 복구
        return;
    }

    for(int i = 0; i<spaceVec.size(); i++){
        if(picked[i] == 0){
            picked[i] = 1;
            pickedIdxVec.push_back(i);
            pickDFS(toPick-1);
            pickedIdxVec.pop_back();
            picked[i] = 0;
        }
    }
}

int main()
{
    
    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) spaceVec.push_back(make_pair(i,j));
        }
    }


    //상대편 그룹의 시작 위치 찾기
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if(map[i][j] == 2 && visited[i][j] == 0){
                partnerGroup_StartLoc.push_back(make_pair(i,j));
                BFS(i,j);
            }
        }
    }

    //빈공간에서 내 돌 놓을 곳 2개 고르기 -> 완전탐색
    pickDFS(2);
    cout << answer;

    return 0;
}