1. 문제
https://www.acmicpc.net/problem/1799
2. 문제의 요구
체스에서 대각선으로 공격할 수 있는 "비숍"을 서로 공격하지 못하도록
체스판에 배치할 수 있는 최대 개수를 구하여라.
3. 풀이
#적용할 알고리즘 : 백트래킹
일단은 단순하게 모든 칸에 대해 각 비숍을 배치할 때 마다
그 대각선 방향에 전에 배치했던 비숍의 유무를 확인하고 없다면
그 자리에 배치하는 방식의 알고리즘을 생각할 수 있다.
하지만 이런 방식은 시간초과가 났다.
여기서 새로운 발상이 필요한데 그것은 바로
#새로운 발상 : 비숍을 놓을 때 체스판의 검은 부분과 흰 부분은 서로 관련이 없다.
비숍을 흰 부분에 놓으면 그 비숍이 공격할 수 있는 곳은 흰 부분 뿐이다.
따라서 체스판의 흰 부분과 검은 부분을 분리하여 따로 백트래킹한다.
이렇게 하면 (10 * 10) = 100 에서 ((5 * 5) * 2) = 50 이 되기 때문에 확실한 이득을 볼 수 있다.
4. 코드
#include<iostream>
#include<string>
#include<stack>
#include<tuple>
#include<queue>
#include<algorithm>
#include<bitset>
using namespace std;
#define endl (cout << '\n')
int dx[4] = { 1, -1, 1, -1 };
int dy[4] = { 1, -1, -1, 1 };
int n;
int board[12][12];
bool isUsed[12][12];
vector<pair<int, int>> white;
vector<pair<int, int>> black;
int mx = 0;
//대각선 라인에 다른 비숍이 있는지 확인
//있으면 => 되돌아감
//없으면 => 계속
bool Check(int x, int y)
{
for (int dir = 0; dir < 4; dir++)
{
for (int i = 0; true; i++)
{
if (x + i * dx[dir] < 0 || x + i * dx[dir] >= n || y + i * dy[dir] < 0 || y + i * dy[dir] >= n) break;
//cout << x << ' ' << y << '\n';
//cout << i << ' ' << dx[dir] << ' ' << dy[dir] << ' ' << x + i * dx[dir] << ' ' << y + i * dy[dir] << '\n';
if (isUsed[x + i * dx[dir]][y + i * dy[dir]])
{
return false;
}
}
}
return true;
}
//백트래킹
void solve(int cur, vector<pair<int, int>>& color, int start)
{
mx = max(mx, cur);
if (cur == color.size()) return;
for (int i = start; i < color.size(); i++)
{
int cx, cy;
tie(cx, cy) = color[i];
if (isUsed[cx][cy]) continue;
if (Check(cx, cy))
{
isUsed[cx][cy] = 1;
solve(cur + 1, color, i + 1);
isUsed[cx][cy] = 0;
}
}
}
bool isWhite[12][12];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i += 2) isWhite[0][i] = 1;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < n; j++)
{
isWhite[i][j] = (isWhite[i - 1][j] ? false : true);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> board[i][j];
if (board[i][j] == 1)
{
///화이트 칸과 블랙 칸을 나눠서 벡터에 저장
if (isWhite[i][j]) white.push_back({i, j});
else black.push_back({ i, j });
}
}
}
int ans = 0;
//화이트 칸과 블랙칸이
//서로 연관이 없기 때문에 가능하다
//화이트 칸에서 비숍 배치
solve(0, white, 0);
ans += mx;
mx = 0;
//블랙 칸에서 비숍 배치
solve(0, black, 0);
ans += mx;
cout << ans;
}
5. 느낀 점
시간을 줄일 방법이 생각이 안나서 결국 답을 찾아봤다.
이런 발상을 좀 더 쉽게 할 수 있도록 계속 생각해야한다.
'알고리즘&자료구조 실전문제풀이 > 백트래킹' 카테고리의 다른 글
Boj 2580 스도쿠 (0) | 2023.04.16 |
---|---|
boj 16987 계란으로 계란치기 (0) | 2023.04.14 |