https://www.acmicpc.net/problem/1799
백트래킹을 사용해 풀 수 있는 문제입니다. n-queen 문제와 비슷하게 비숍을 하나씩 놓는다고 생각하고, 하나의 비숍이 놓일 때 그 대각선에 있는 칸들은 전부 갈 수 없다고 표시해주면 됩니다. 다만 나이브하게 백트래킹을 돌리면 시간초과를 받게 되고, 체스칸의 흰색 영역과 검정색 영역을 나눠서 (비숍은 한 색으로만 이동할 수 있으므로) 풀면 풀 수 있습니다. 이 아이디어를 생각하는 것이 어려웠습니다.
아래는 코드입니다.
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
//2d graph search////////////////////////////////////////////////////////////////////
bool inrange(int i, int j, int n, int m) { return 0 <= i && i < n && 0 <= j && j < m; }
/////////////////////////////////////////////////////////////////////////////////////
using namespace std;
int T, n, graph[15][15];
int cnt, ans;
vector<int> vec;
int bw(int x, int y) {
return ((x % 2) + (y % 2)) % 2;
}
void check(int pos, int op) {
int x = pos / n;
int y = pos % n;
for (int i = 1; i <= 10; i++) {
if (inrange(x + i, y + i, n, n)) graph[x + i][y + i] += op;
if (inrange(x + i, y - i, n, n)) graph[x + i][y - i] += op;
if (inrange(x - i, y + i, n, n)) graph[x - i][y + i] += op;
if (inrange(x - i, y - i, n, n)) graph[x - i][y - i] += op;
}
}
void find(int pos) {
cnt++;
ans = max(ans, cnt);
check(pos, 1);
for (int i = pos + 1; i < n * n; i++) {
int x = i / n;
int y = i % n;
if (bw(pos / n, pos % n) != bw(x, y)) continue;
if (graph[x][y]) continue;
find(i);
}
cnt--;
check(pos, -1);
}
int32_t main(void) {
FastIO;
T = 1;
//cin >> T;
while (T--) {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x;
cin >> x;
if (!x) graph[i][j]++;
}
}
int ans1 = 0;
int ans2 = 0;
for (int i = 0; i < n * n; i++) {
if (bw(i / n, i % n)) continue;
if (graph[i / n][i % n]) continue;
find(i);
ans1 = max(ans, ans1);
ans = 0;
cnt = 0;
}
for (int i = 0; i < n * n; i++) {
if (!bw(i / n, i % n)) continue;
if (graph[i / n][i % n]) continue;
find(i);
ans2 = max(ans, ans2);
ans = 0;
cnt = 0;
}
cout << ans1 + ans2 << endl;
}
return 0;
}
'알고리즘 문제해결 > BOJ' 카테고리의 다른 글
BOJ 2647 검은점과 하얀점 (0) | 2022.08.14 |
---|---|
BOJ 15961 회전 초밥 (0) | 2022.08.12 |
BOJ 2671 잠수함식별 (0) | 2022.08.10 |
BOJ 14867 물통 (0) | 2022.08.10 |
BOJ 1691 석판 (0) | 2022.08.09 |