🎲문제
주소:백준 1799
서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.
< 그림 1 >
그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.
< 그림 2 >
< 그림 3 >
정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.
⌨ 입력
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.
✅ 풀이
풀이방법
DFS를 활용한 백트래킹 문제이다. 단순히 DFS를 사용하는 것 뿐만 아니라 어떻게 하면 더 시간을 줄일수 있는지 고민 해야하는 문제였다. 초기엔 단순히 놓을 수 있는 모든 배열을 접근하여 DFS를 돌리는 방식으로 접근했지만 시간초과를 받았다. 여기저기 검색하고 찾아본 결과, 체스판의 흰색 과 검은색 타일의 비숍은 서로 충돌할 일이 없으므로 흰타일, 검은 타일 두 가지 경우로 나누어 더한다면, N/2의 시간단축 효과를 볼 수 있었다.
- 체스 보드의 넓이 N을 입력받고 전체 타일 정보를 입력받는다.
- 흰 타일에 비숍을 배치하는경우(v), 검은 타일에 비숍을 배치하는경우(v2), 두가지 경우로 벡터를 생성하여 배치가 가능한 위치일 때 벡터에 좌표를 집어 넣는다.
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int num;
cin >> num;
board[i][j] = num;
if (num == 1) {
if (((i + j) % 2) == 1) v.push_back({ i, j });
else v2.push_back({ i, j });
}
}
}
}- v.size()와 v2.size() 각각 dfs를 따로 돌려준다.
- 각 결과를 저장하여 더함으로써 결과를 출력 할 수 있다.
void solve() {
for (int i = 0; i < v.size(); i++) dfs(i, 0, v);
int tmp = result;
result = 0;
for (int i = 0; i < v2.size(); i++) dfs(i, 0, v2);
cout << result + tmp;
}- 벡터의 인덱스값, 벡터, 비숍의 개수를 인자로 받는 dfs함수를 작성한다.
- 인덱스값이 벡터의 사이즈만큼 왔을 때(모든 가능한 경우를 순회했을 때), 순회했을 때 비숍의 개수와 기존 비숍 최댓값을 비교해서 더 큰값을 저장한다.
- 해당 인덱스의 좌표가 비숍이 위치 가능한 좌표인 경우, board에 표시하고 인덱스 크기, 비숍의 개수를 추가해서 dfs를 실행한다.
- 또한 인덱스가 마지막 값이 아닌 모든경우에도 인덱스 값을 증가시켜 dfs함수로 순회한다.
void dfs(int index, int cnt, vector<pair<int, int>> v ) {
if (index == v.size()) {
result = max(cnt,result);
return;
}
int x = v[index].first;
int y = v[index].second;
if (chk_bishop(x, y)) {
board[x][y] = -1;
dfs(index + 1, cnt + 1, v);
board[x][y] = 1;
}
dfs(index + 1, cnt, v);
return;
}전체 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, result;
vector<pair<int, int>> v;
vector<pair<int, int>> v2;
int board[10][10] = {0,};
int direction[4][2] = { {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
void init();
void solve();
void dfs(int, int, vector<pair<int, int>>);
bool chk_bishop(int, int);
bool is_inside(int);
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int num;
cin >> num;
board[i][j] = num;
if (num == 1) {
if (((i + j) % 2) == 1) v.push_back({ i, j });
else v2.push_back({ i, j });
}
}
}
}
void solve() {
for (int i = 0; i < v.size(); i++) dfs(i, 0, v);
int tmp = result;
result = 0;
for (int i = 0; i < v2.size(); i++) dfs(i, 0, v2);
cout << result + tmp;
}
void dfs(int index, int cnt, vector<pair<int, int>> v ) {
if (index == v.size()) {
result = max(cnt,result);
return;
}
int x = v[index].first;
int y = v[index].second;
if (chk_bishop(x, y)) {
board[x][y] = -1;
dfs(index + 1, cnt + 1, v);
board[x][y] = 1;
}
dfs(index + 1, cnt, v);
return;
}
bool chk_bishop(int x, int y) {
for (int i = 1; i < N; i++) {
for (int j = 0; j < 4; j++) {
int tmp = x + (direction[j][0] * i);
int tmp2 = y + (direction[j][1] * i);
if (is_inside(tmp) && is_inside(tmp2)) {
if (board[x + (direction[j][0] * i)][y + (direction[j][1] * i)] == -1)
return false;
}
}
}
return true;
}
bool is_inside(int x) {
return (0 <= x && x < N);
}
int main() {
init();
solve();
return 0;
}