[BaekJoon] 1799번 - 비숍 [Java][C++]
1. 아이디어
체스판에서 각 칸에 비숍을 놓을 수 있는지 없는지 정보가 주어졌을 때 가장 많이 배치할 수 있는 비숍의 개수를 구하는 문제다. 체스를 해본 적이 있다면 감을 잡을 수 있는데 체스판은 가장 왼쪽 위 칸이 하얀색이며 하얀색과 검은색이 반복되어 나타나는 구조이고 비숍은 처음 놓인 칸의 색에서 다른 색을 공격할 수 없다.
해당 문제는 체스판의 각 대각선을 그룹으로 묶어줘서 해결했는데 5 by 5 크기의 체스판에서 행과 열의 번호를 표시하면 아래와 같다.
우상에서 좌하 방향 대각선을 같은 그룹으로 묶으려면 행 번호와 열 번호의 합이 같은 두 칸은 같은 대각선에 있다고 생각하면 된다.
좌상에서 우하 방향 대각선을 같은 그룹으로 묶으려면 행 번호와 열 번호의 차가 같은 두 칸은 같은 대각선에 있다고 생각하면 된다. 숫자를 0부터 시작하기 위해 모든 칸에 4를 더해줬다.
구현은 먼저 행 번호와 열 번호의 합을 인덱스와 매핑한 배열을 활용했다. 배열의 원소로는 리스트(벡터)를 갖게 해서 특정 대각선에 위치한 비숍을 놓을 수 있는 좌표들을 해당 대각선 번호로 조회할 수 있게 했다. 행 번호와 열 번호의 합을 인덱스와 매핑하므로 우상에서 좌하 방향으로 같은 대각선에 있으면 같은 리스트(벡터)에 들어 있게 된다.
탐색은 하얀 칸과 검은 칸에서 각각 한번씩 수행을 해줬다. 하얀 칸과 검은 칸은 서로에게 아무 영향도 끼치지 않으므로 각각 돌리면 백트래킹 성능을 훨씬 향상할 수 있다.(안해도 통과가 되긴 한다.) 한번에 돌리면 바로 개수를 출력하면 되지만 각각 돌리면 하얀 칸에 배치할 수 있는 최대 개수와 검은 칸에 배치할 수 있는 최대 개수의 합을 출력하면 된다.
탐색 파라미터로는 우상 좌하 방향 대각선의 번호와 재귀 깊이를 넘겨줬다. 각 대각선에 대해 하나를 뽑고 다음 대각선으로 넘어가야 하므로 대각선 번호가 필요했고 색깔별로 탐색을 하므로 다음 대각선의 번호는 현재 번호 +2다. 재귀 깊이는 현재 탐색 깊이에서 배치한 비숍의 수와 동일해서 모든 대각선을 다 고려했으면 최대 개수를 갱신해주면 된다. 현재 위치에 비숍을 놓을지 판단할 때는 우상 좌하 대각선을 이미 고려했으므로 좌상 우하 대각선에 대한 배치만 고려하면 되는데 이를 위해 방문 체크를 수행했고, 현재 대각선에 비숍을 배치하지 않아도 다음 대각선으로 넘어가야 해서 플래그를 하나 두어서 다음 대각선으로 넘어갈 수 있게 해줬다.
2. 코드
1. 풀이 [Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.io.*;
import java.util.*;
public class Main {
static final int MX = 10;
static int n;
static boolean[] d = new boolean[MX * 2]; // 좌상에서 우하 방향 대각선
static int cnt;
static List<int[]>[] poslist = new ArrayList[MX * 2];
static {
for (int i = 0; i < MX * 2; i++) {
poslist[i] = new ArrayList<>();
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int x = Integer.parseInt(st.nextToken());
if (x == 1) poslist[i + j].add(new int[]{i, j});
}
}
int ans = 0;
cnt = 0;
solve(0, 0); // 하얀색 칸에 대한 비숍 배치
ans += cnt;
cnt = 0;
solve(1, 0); // 검은색 칸에 대한 비숍 배치
ans += cnt;
System.out.println(ans);
}
static void solve(int idx, int depth) {
if (idx >= 2 * n - 1) {
cnt = Math.max(cnt, depth);
return;
}
boolean flag = false;
for (int[] pos : poslist[idx]) {
int r = pos[0];
int c = pos[1];
if (d[r - c + n - 1]) continue;
d[r - c + n - 1] = true;
solve(idx + 2, depth + 1);
d[r - c + n - 1] = false;
flag = true;
}
if (!flag) {
solve(idx + 2, depth);
}
}
}
2. 풀이 [C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int MX = 10;
int n;
vector<pair<int, int>> poslist[MX * 2];
bool d[MX * 2]; // 좌상에서 우하 방향 대각선
int cnt;
void solve(int idx, int depth) {
if (idx >= 2 * n - 1) {
cnt = max(cnt, depth);
return;
}
bool flag = false;
for (auto [r, c] : poslist[idx]) {
if (d[r - c + n - 1]) continue;
d[r - c + n - 1] = true;
solve(idx + 2, depth + 1);
d[r - c + n - 1] = false;
flag = true;
}
if (!flag) {
solve(idx + 2, depth);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x;
cin >> x;
if (x == 1) poslist[i + j].push_back({i, j});
}
}
int ans = 0;
cnt = 0;
solve(0, 0); // 하얀색 칸에 대한 비숍 배치
ans += cnt;
cnt = 0;
solve(1, 0); // 검은색 칸에 대한 비숍 배치
ans += cnt;
cout << ans;
}
3. 디버깅
그리디한 배치 해법이 있지 않을까 했는데 확신이 없어서 안정적인 백트래킹으로 선회했다.
우상 좌하 방향 대각선으로 후보군을 그룹핑하고 백트래킹을 돌려도 탐색량이 많지 않나 의심했는데 생각보다 빨랐다.
4. 참고
없음.