[백준 / BOJ] 16988 :: Baaaaaaaaaduk2 (Easy)

www.acmicpc.net/problem/16988

16988번: Baaaaaaaaaduk2 (Easy)

Easy..? 다들 알고리즘 잘하시나봐요..이게 easy라니 ㅠ 

 

문제 : 

우선, 앞에 장황한 쓸데없는 설명은 안읽어도 됩니다.

결론적으로 말하면, 우리는 돌 두개를 놓을 것인데, 돌 두개를 놓아서 상대방 돌을 최대한 많이 따먹어야 합니다.

 

상대방 돌을 딸 수 있는 조건은

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

이렇게 인데, 이해가 조금 힘들죠

 

이걸 조금 반대로 생각하면 이해가 쉽습니다. 어떤 그룹이 둘러싸여짐을 당하려면, 그 그룹의 모든 돌의 인접한 칸이 상대방 돌이어야만 하는 것입니다. 즉 빈칸이 존재하면 안된다는 뜻.

 

예를 들어볼게요

이렇게 되어있는 예시에서, 색칠한 그룹이 둘러싸여지려면, 해당 그룹에 포함된 돌의 모든 인접하는 값들이 0이 아니어야 합니다

이렇게 파란색으로 칠한, 모든 인접하는 부분이 0이 아니어야 한다는 뜻!

 

여기서 하나 더 고려할 점이 벽에 맞닿아있는 2번 돌의 경우 벽은 0번(빈칸)으로 치지 않기 때문에 고려를 잘 해주어야 합니다. 

> 인풋을 받기 전 모든 테두리 값을 1로 설정해주면 편합니다.

이렇게 테두리를 설정해주면 편합니다!

 

자 , 그럼 풀이 방법을 생각해 봅시다.

 

 

풀이 

- 우선, 맵 전체를 탐색해서 각 그룹에 인접한 빈칸들을 모두 저장할 것입니다.

왜냐면, 우리는 총 두 개의 돌을 둘 수 있고, 빈칸에 돌을 둘 것이기 때문에 우선 빈칸을 모두 가져오는 것입니다.

BFS를 통해 그룹을 탐색하고 해당 빈칸의 값을 저장합니다.

 

- 빈칸의 값을 모두 가져온 후 완전탐색을 돌립니다. 예를 들어 빈칸이 N개라면 nC2의 가지수가 나오겠죠?

현재 탐색중인 두개의 빈칸(후보군)에 대해, 그 두 빈칸에 돌을 놓았다고 가정하고(1로 값 변경) 다시 맵 전체에 BFS를 돌려서 따먹힌 돌의 개수를 탐색합니다.

 

이해를 위해 첨부합니다.

문제의 예시 6번의 경우

> 테투리 : 초록 , 하늘색 : 2번그룹에 인접한 1번 돌들

 

해당 그림에서 진한 주황색이 각 그룹이 인접한 빈칸이될것입니다

(1,1), (2,2) , (3,4) , (4,5) 

 

따라서 우리는 이 4가지 후보군에서 두개를 고르는 모든 경우의 수를 탐색합니다.

그렇게 탐색을 하다 보면 (3,4) , (4,5) 두 곳에 1번 돌을 놓는 경우가 최댓값이 됩니다!

 

소스코드에 주석 보시면 더 이해하기 쉬울듯합니다

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int N, M, ans = 0;
int map[22][22];
int tmp[22][22];
 
bool visited[22][22];
bool visited2[22][22];
 
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 }; //인접 위치
vector<pair<int,int>> candidate;//돌 두개를 놓을 수 있는 후보군들
 
void bfs(int i, int j) {
    vector<pair<int, int> > tmp;
    queue<pair<int, int> > q;
    q.push({ i,j });
    
    int cnt = 0;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || nx > N + 1 || ny < 0 || ny > M + 1) continue;
            if (map[nx][ny] == 0 && !visited[nx][ny]) { //빈칸이면 돌을 놓아야 할지도 모르는 곳
                cnt++;
                visited[nx][ny] = true;
                tmp.push_back({ nx,ny });
            }
            else if (map[nx][ny] == 2 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({ nx,ny });
            }
        }
    }
 
    for (int i = 0; i < tmp.size(); i++) {
        int x = tmp[i].first;
        int y = tmp[i].second;
        candidate.push_back({ x,y });
    }
 
}
 
int count(int i, int j) {//돌을 놓은 후 따먹힌 그룹의 돌 개수를 count
    queue<pair<int, int> > q;
    q.push({ i,j });
 
    int cnt = 0;
    bool flag = true;
    int zero_cnt = 0;
 
    while (!q.empty()) {
        if (!flag) break;
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        cnt++;
        
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || nx > N + 1 || ny < 0 || ny > M + 1) continue;
            if (tmp[nx][ny] == 0 ) { 
                zero_cnt++;//빈칸의 개수
            }
            else if (tmp[nx][ny] == 2 && !visited2[nx][ny]) {
                visited2[nx][ny] = true;
                q.push({ nx,ny });
            }
        }
    }
    if (zero_cnt > 0) return 0;//빈칸이 하나라도 존재하면 따먹지 못한 그룹
    else return cnt;
}
int main() {
    cin >> N >> M;
    
    //테두리 경계값 1로 설정
    for (int i = 0; i <= M + 1; i++) map[0][i] = 1;
    for (int i = 0; i <= N + 1; i++) map[i][0] = 1;
    for (int i = 0; i <= N + 1; i++) map[i][M + 1] = 1;
    for (int i = 0; i < M + 1; i++) map[N + 1][i] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j] == 2 && !visited[i][j]) {
                visited[i][j] = true;
                bfs(i, j);
            }
        }
    }
    //빈칸 후보군 탐색
 
 
    for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j <= M + 1; j++) {
            visited2[i][j] = false;
        }
    }
 
    //가져온 후보군 중 두개를 선택하는 완전탐색
    for (int i = 0; i < candidate.size(); i++) {
        for (int j = 0; j < candidate.size(); j++) {
            int now = 0;
            if (i == j) continue;
            int x1 = candidate[i].first;
            int y1 = candidate[i].second;
            int x2 = candidate[j].first;
            int y2 = candidate[j].second;
            
            for (int x = 0; x <= N + 1; x++) {
                for (int y = 0; y <= M + 1; y++) {
                    tmp[x][y] = map[x][y];
                    visited2[x][y] = false;
                }
            }
            tmp[x1][y1] = 1;
            tmp[x2][y2] = 1;
            
            for (int x = 0; x <= N + 1; x++) {
                for (int y = 0; y <= M + 1; y++) {
                    if (!visited2[x][y] && tmp[x][y] == 2) {
                        visited2[x][y] = true;
                        now += count(x, y);
                    }
                }
            }
            if (ans < now) ans = now;
 
        }
 
    }
    cout << ans << endl;
 
}