(BOJ) 16988 Baaaaaaaaaduk2 (Easy)

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

문제 풀이:

1. 흑의 그룹을 찾아서 저장한다.  -> bfs()

  - vector<vector<P>> v;

  - v[0] : 첫번째 그룹 

  - v[0].push_back({ x좌표,y좌표 })   // v[0] 그룹의 좌표값 저장

2. 돌 두개를 둘 곳 선정 

 - 이중포문 사용

 - 배열을

0	1	2
3	4	5
6	7	8

                    로 생각하고 가로가 m일 때 좌표의 위치는 ( i/m, i%m )이다.

3. 둘러쌓인 흑의 그룹이 몇개인지 카운트 -> func()

소스코드:

#include <iostream> #include <queue> #include <vector> #include <string> #include <string.h> #include <tuple> #include <algorithm> #define inf 987654321 using namespace std; typedef pair<int, int> P; int n, m,arr[21][21],t,res; int dx[4] = { 0,1,0,-1 }; int dy[4] = { -1,0,1,0 }; bool visit[21][21],dist[402][402]; vector<vector<P>> v; void bfs(int cur_x,int cur_y) { queue<P> q; q.push({ cur_x,cur_y }); v[t].push_back({ cur_x,cur_y }); visit[cur_x][cur_y]=true; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx < 0 || xx >= n || yy < 0 || yy >= m || visit[xx][yy]||arr[xx][yy]!=2) continue; visit[xx][yy] = true; v[t].push_back({ xx,yy }); q.push({ xx,yy }); } } t++;  } void func() { int tmp = 0; for (int i = 0; i < t; i++) { bool check = true; for (int j = 0; j<v[i].size(); j++) { for (int k = 0; k < 4; k++) { int x = v[i][j].first+dx[k]; int y = v[i][j].second+dy[k]; if (x >= 0 && x < n && y >= 0 && y < m && arr[x][y] == 0) { check = false; break; } } } if (check) tmp += v[i].size(); } res = max(res, tmp); } int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> arr[i][j]; } } v.resize(250); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] == 2 && !visit[i][j]) bfs(i, j); } } for (int i = 0; i < n*m; i++) { if (arr[i / m][i%m] != 0) continue; for (int j = 0; j < n*m; j++) { if (i == j|| arr[j / m][j%m] != 0||dist[i][j]) continue; arr[i / m][i%m] = 1; arr[j / m][j%m] = 1; dist[i][j] = true; func(); arr[i / m][i%m] = 0; arr[j / m][j%m] = 0; } } cout << res << '\n'; return 0; }