펭로그

[C++] 백준 BOJ 1986 체스 본문

Study/PS(Algorithm)

[C++] 백준 BOJ 1986 체스

노랑펭귄 2019. 2. 20. 18:41

문제링크 : https://noj.am/1986


간단하면서도 지저분한 시뮬레이션 문제로 보인다.

최대한 깔끔하게 하기 위해서 define을 사용하여 직관성을 높였으며 queen과 knight의 이동시 조건을 고려하여 별도의 함수로 구성하였다.


문제를 풀이할 때 주의할 점은 Queen 말이 이동할 때 장애물에 가로막혀있으면 이동 못한다는 점이다.

풀이시에 안전하지 않는 영역은 'X'로 만들어 두었고 장애물 체크는 board[x][y] == 0 (빈공간) 상태일때만 체크했었는데 올바른 답이 나오지 않는 실수를 풀이 과정에서 겪었다.

5번째 줄에서 적어놓은 것처럼 Q, K, P가 아닐 경우라고 명시해주니 쉽게 풀 수 있었다.

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
69
70
71
72
73
74
75
76
77
78
79
80
81
// BOJ_1986 체스
#include <iostream>
 
#define CHK_RANGE (nx >= 1 && nx <= N && ny >= 1 && ny <= M)
#define CHK_BRR(X, Y) (board[X][Y] != 'Q' && board[X][Y] != 'K' && board[X][Y] != 'P')
using namespace std;
 
char board[1002][1002];
int N, M; // 보드 크기
 
inline void queen(int x, int y) {
    int dx[] = {00-11-1-111};
    int dy[] = {-1100-11-11};
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        while (CHK_RANGE && CHK_BRR(nx, ny)) {
            board[nx][ny] = 'X';
            nx += dx[i];
            ny += dy[i];
        }
    }
}
 
void knight(int x, int y) {
    int dx[] = {-2-222-1-111};
    int dy[] = {-11-11-22-22};
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (CHK_RANGE && CHK_BRR(nx, ny))
            board[nx][ny] = 'X';
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    cin >> N >> M;
 
    // Q, K, P 순서로 3회 반복 입력
    for (int i = 0; i < 3; i++) {
        int num;
        cin >> num;
        for (int ii = 0; ii < num; ii++) {
            int x, y;
            cin >> x >> y;
            if (i == 0)
                board[x][y] = 'Q';
            else if (i == 1)
                board[x][y] = 'K';
            else
                board[x][y] = 'P';
        }
    }
 
    // 완전탐색 시뮬
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (board[i][j] == 'Q')
                queen(i, j);
            else if (board[i][j] == 'K')
                knight(i, j);
        }
    }
 
    // 결과 카운팅
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (board[i][j] == 0)
                cnt++;
        }
    }
    cout << cnt;
 
    return 0;
}
cs


Comments