백준 16988
문제링크
https://www.acmicpc.net/problem/16988
문제
풀이
모든 경우의 수를 생각하여 bfs를 돌려주며 풀었다.
크게 해야하는 작업은 다음의 두가지 이다.
-
내 돌을 놓은 두 자리를 찾아서 돌을 놓아보기
-
백트래킹과 next_permutation 알고리즘을 이용하여 놓을 두 자리를 골라낼 수 있다.
-
아래 코드에서는 next_permutation을 이용했다.
-
-
놓은 돌을 기준으로 현재의 바둑판에서 딸 수 있는 돌이 몇개인지 세기
-
1번에서 돌을 놓은 각 경우에 대해 현재 바둑판의 상태에서 딸 수 있는 돌이 몇개인지 count를 해주었다.
-
카운트 하는 방법은 맵을 훑으면서 적의 돌인 경우 큐에 집어넣고 bfs를 돌려준다.
-
bfs를 돌리는 과정에서 적의 돌에 빈공간(0)이 인접한 경우가 있었다면 0을 return 해준다.
-
그렇지 않다면 세준 돌의 개수를 return 해준다.
-
코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct {
int x;
int y;
}pos;
int n, m, ans;
int maps[21][21];
bool vi[21][21];
queue<pos> q;
int dx[4]{ 0,0,1,-1 };
int dy[4]{ 1,-1,0,0 };
int bfs(int x, int y, int type) {
int cnt = 1;
int check = 1;
q.push({ x,y });
vi[x][y] = true;
while (!q.empty()) {
int nowx = q.front().x;
int nowy = q.front().y;
q.pop();
for (int i = 0; i < 4; i++) {
int nextx = nowx + dx[i];
int nexty = nowy + dy[i];
if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if (!vi[nextx][nexty]) {
if (maps[nextx][nexty] == 0) check = 0;
else if (maps[nextx][nexty] == type) {
q.push({ nextx,nexty });
vi[nextx][nexty] = true;
cnt++;
}
}
}
}
if (check) return cnt;
else return 0;
}
int simulation() {
fill(&vi[0][0], &vi[20][21], false);
int total_cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maps[i][j] == 2 && !vi[i][j]) {
total_cnt += bfs(i, j, maps[i][j]);
}
}
}
return total_cnt;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> maps[i][j];
}
}
vector<int> sel;
for (int i = 0; i < n * m - 2; i++) sel.push_back(0);
for (int i = 0; i < 2; i++) sel.push_back(1);
do {
vector<pos> selected;
for (int i = 0; i < sel.size(); i++) {
if (sel[i] == 1) {
int x = i / m;
int y = i % m;
if (maps[x][y] == 0) selected.push_back({ x,y });
}
}
if (selected.size() == 2) {
for (int i = 0; i < 2; i++) maps[selected[i].x][selected[i].y] = 1;
ans = max(ans, simulation());
for (int i = 0; i < 2; i++) maps[selected[i].x][selected[i].y] = 0;
}
} while (next_permutation(sel.begin(), sel.end()));
cout << ans;
}
후기
익숙한 유형이라 빨리 풀려고 하다보니까 코드가 난잡해지는것 같다.
Author And Source
이 문제에 관하여(백준 16988), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bgg01578/백준-16988저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)