문제
서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.
![](https://blog.kakaocdn.net/dn/brn5wy/btrDV6aH9hA/ZP3uxAPMlr26M897qz4Mw0/img.jpg)
< 그림 1 >
그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.
![](https://blog.kakaocdn.net/dn/bNlkRd/btrD0rSfHOD/uBDbKhvPgICJRKQz6ho421/img.jpg)
< 그림 2 >
![](https://blog.kakaocdn.net/dn/YrCRZ/btrDWSDAzmr/9cthV9JxKkEnPGb05sOngK/img.jpg)
< 그림 3 >
정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.
출력
첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.
테스트 케이스
입력 1
10
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
출력 1
18
입력 2
3
1 0 1
0 1 0
1 1 1
출력 2
3
입력 3
3
0 1 0
1 1 1
1 0 1
출력 3
4
접근
백트래킹 해주는 문제인데, 그냥 단순히 했더니 시간초과가 났습니다. 시간제한을 10초나 준 이유가 있는 것 같습니다 ㅋㅋ
체스판이기 때문에 흰색부분과 검은색부분은 서로 절대 영향을 주지 않으므로, 이를 따로 dfs 돌림으로써 dfs 깊이를 조절하여 시간을 절약했습니다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int N, map[][];
static int result = 0;
public static void dfs(int x, int y, int cnt,int state) {
if (x >= N && y > N) {
result = Math.max(result, cnt);
return;
}
if (y >= N + 1) {
if(state == 1) state =2;
else state = 1;
dfs(x + 1, state, cnt, state);
return;
}
if (x >= N + 1) {
return;
}
if (map[x][y] == 1) {
if (canSet(x, y)) {
map[x][y] = 2;
dfs(x, y + 2, cnt + 1, state);
map[x][y] = 1;
dfs(x,y+2,cnt,state);
} else {
dfs(x, y + 2, cnt,state);
return;
}
}
else {
dfs(x,y+2,cnt,state);
return;
}
}
public static boolean canSet(int x, int y) {
for (int i = 1; i <= N; i++) {
if (x + i <= 0 || x + i > N || y + i <= 0 || y + i > N)
break;
if (map[x + i][y + i] == 2) {
return false;
}
}
for (int i = 1; i <= N; i++) {
if (x - i <= 0 || x - i > N || y - i <= 0 || y - i > N)
break;
if (map[x - i][y - i] == 2) {
return false;
}
}
for (int i = 1; i <= N; i++) {
if (x + i <= 0 || x + i > N || y - i <= 0 || y - i > N)
break;
if (map[x + i][y - i] == 2) {
return false;
}
}
for (int i = 1; i <= N; i++) {
if (x - i <= 0 || x - i > N || y + i <= 0 || y + i > N)
break;
if (map[x - i][y + i] == 2) {
return false;
}
}
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(1, 1, 0, 1);
dfs(1,2,result,2);
System.out.println(result);
br.close();
}
}
주의
시간초과 주의
'공부 정리 > 백준' 카테고리의 다른 글
[백준] 16397 탈출 java (0) | 2023.02.01 |
---|---|
[백준] 2233 사과나무 자바 (0) | 2022.07.05 |
[백준] 자바 16562 친구비 (0) | 2022.06.17 |
[백준] 자바 15900 나무 탈출 (0) | 2022.06.13 |
[백준] 자바 23807 두 단계 최단 경로 3 (0) | 2022.06.03 |
댓글