이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2570번 : '비숍2', 1799번 : '비숍' 문제의 풀이 코드와 해설을 다룹니다.
문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다. (1799번의 비숍 문제의 난이도는 Gold I이지만, 이 포스트에서는 더 어려운 문제를 기준으로 풀이를 다룹니다.)
2570번 : 비숍2
2570번: 비숍2
첫째 줄에 정사각형 체스판의 크기 N이 주어진다. 둘째 줄에는 체스판 위에 놓인 장애물의 개수 M이 주어진다. N은 100이하의 자연수이고 M은 음이 아닌 정수이다. 이어 셋째 줄부터 한 줄에 하나
www.acmicpc.net
위와 같이 체스판 위의 일부 칸에 장애물이 주어질 때, 체스에서 대각선으로만 움직이는 비숍이 서로 공격하지 못하도록 최대로 놓았을 때 몇 개 놓을 수 있는지를 구하는 문제입니다.
[백준/BOJ] 9525번 : 룩 배치하기 / 1760번 : N-Rook (이분 매칭)
이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 9525번 : '룩 배치하기', 1760번 : 'N-Rook' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum III에 해당..
restudycafe.tistory.com
↑ 풀이의 대략적인 아이디어는 위의 문제의 풀이와 비슷합니다.
이전에 풀이했던 최대 룩 문제와 비슷하지만, 비숍의 경우에는 대각선으로 움직이기 때문에 행과 열의 번호를 매기기 상당히 까다로운 부분이 있습니다.
규칙성을 찾아보자면, 왼쪽 아래 방향으로 대각선을 긋는 경우는 i-j 값으로 그 줄의 번호를 파악해주면 되고, 오른쪽 아래 방향으로 대각선을 긋는 경우는 i+j 값으로 그 줄의 번호를 파악할 수 있습니다.
↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MSIZE = 105, MAX = 5005;
vector<int> Adj[MAX];
int Left[MAX], Right[MAX];
bool Visit[MAX];
bool DFS(int from) {
Visit[from] = true;
for(int i=0; i<Adj[from].size(); i++) {
int to = Adj[from][i];
if(Right[to] == -1 || (!Visit[Right[to]] && DFS(Right[to]))) {
Left[from] = to, Right[to] = from;
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
bool Obs[MSIZE][MSIZE] = {};
while(M--) {
int i, j; cin >> i >> j;
Obs[i][j] = true;
}
int rNum[MSIZE][MSIZE] = {}, cNum[MSIZE][MSIZE] = {}, cnt = 1;
for(int k=-(N-1); k<=N-1; k++) {
int i, j;
if(k < 0) i = 1, j = i-k;
else j = 1, i = j+k;
while(i <= N && j <= N) {
if(!Obs[i][j]) {
rNum[i][j] = cnt;
if(i == N || j == N || (i < N && j < N && Obs[i+1][j+1])) cnt++;
}
i++, j++;
}
}
int rCnt = cnt; cnt = 1;
for(int k=2; k<=N*2; k++) {
int i, j;
if(k <= N) i = 1, j = k-i;
else j = N, i = k-j;
while(i <= N && j >= 1) {
if(!Obs[i][j]) {
cNum[i][j] = cnt;
if(i == N || j == 1 || (i < N && j > 1 && Obs[i+1][j-1])) cnt++;
}
i++, j--;
}
}
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(!Obs[i][j]) Adj[rNum[i][j]].push_back(cNum[i][j]);
int match = 0;
fill(Left, Left+MAX, -1), fill(Right, Right+MAX, -1);
for(int i=1; i<=rCnt; i++) {
fill(Visit, Visit+MAX, false);
if(DFS(i)) match++;
}
cout << match;
}
핵심 아이디어는 대각선으로 이루어진 줄의 번호를 어떻게 잘 넘버링하냐와, 줄의 두 그룹 간의 이분 매칭을 수행하는 부분이라고 할 수 있습니다.
풀이 코드를 제출하면 위와 같은 기록으로 통과할 수 있습니다.
1799번 : 비숍
1799번: 비숍
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로
www.acmicpc.net
위 문제의 풀이를 이용하면 이 문제 역시 똑같은 방식으로 풀이가 가능합니다.
심지어 이 문제는 하위 버전이기 때문에, 벽을 고려할 필요 없이 같은 줄이면 그냥 똑같이 넘버링을 해주면 됩니다.
↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MSIZE = 105, MAX = 5005;
vector<int> Adj[MAX];
int Left[MAX], Right[MAX];
bool Visit[MAX];
bool DFS(int from) {
Visit[from] = true;
for(int i=0; i<Adj[from].size(); i++) {
int to = Adj[from][i];
if(Right[to] == -1 || (!Visit[Right[to]] && DFS(Right[to]))) {
Left[from] = to, Right[to] = from;
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int Board[MSIZE][MSIZE] = {};
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) cin >> Board[i][j];
int rNum[MSIZE][MSIZE] = {}, cNum[MSIZE][MSIZE] = {}, cnt = 1;
for(int k=-(N-1); k<=N-1; k++) {
int i, j;
if(k < 0) i = 1, j = i-k;
else j = 1, i = j+k;
while(i <= N && j <= N) {
rNum[i][j] = cnt;
if(i == N || j == N) cnt++;
i++, j++;
}
}
int rCnt = cnt; cnt = 1;
for(int k=2; k<=N*2; k++) {
int i, j;
if(k <= N) i = 1, j = k-i;
else j = N, i = k-j;
while(i <= N && j >= 1) {
cNum[i][j] = cnt;
if(i == N || j == 1) cnt++;
i++, j--;
}
}
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
if(Board[i][j]) Adj[rNum[i][j]].push_back(cNum[i][j]);
int match = 0;
fill(Left, Left+MAX, -1), fill(Right, Right+MAX, -1);
for(int i=1; i<=rCnt; i++) {
fill(Visit, Visit+MAX, false);
if(DFS(i)) match++;
}
cout << match;
}
풀이 코드를 제출하면 위와 같은 기록으로 통과할 수 있습니다.