[ baekjoon ] #1986 체스

백준 #1986 체스

문제 요약

---

• n×m 크기의 체스 판과 Queen, Knight, Pawn의 위치가 주어진다.
• Queen은 가로, 세로, 대각선으로 갈 수 있는 만큼 최대한 이동
  (장애물이 있다면 이동 불가능)
• Knight는 2×3 직사각형을 그렸을 때, 반대쪽 꼭짓점으로 이동
  ↓ 8칸이 해당된다. (장애물이 있어도 이동 가능)
  
• pawn은 상대팀의 말은 잡을 수 없다. (장애물 역할)

💡Idea

1. Queen, Knight, Pawn의 개수와 그 개수만큼 위치를 어떻게 입력 받을까?
   → 개수를 먼저 입력 받은 후 그 개수만큼 반복한다.
2. 말의 종류를 어떻게 구분할까?
   → Queen은 1, Knight는 2, Pawn은 3으로 저장
3. 체스판 전체를 돌면서
   1) Queen 이라면 상,하,좌,우,대각선 총 8방향으로 이동하는 함수 queen() 호출
   2) Knight 라면 2×3 직사각형의 반대쪽 꼭짓점으로 이동하는 함수 knight() 호출
   3) Pawn 은 이동할 수 없으니 아무것도 하지 않음

• 주의할 점 : Queen으로 이동한 위치라도 Knight가 이동 가능 !

[ Source Code ]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
queue <pair<int, int>> tmp;

void move(int dx, int dy, vector <vector<int>> &chess) {
    while(!tmp.empty()) {
        pair<int, int> now = tmp.front(); // 현재 위치
        tmp.pop();
        int nx = now.first + dx;
        int ny = now.second + dy;
        if(nx > 0 && nx <= n && ny > 0 && ny <= m) {
            if(chess[nx][ny] == 0 || chess[nx][ny] == 4) {
                chess[nx][ny] = 4;
                tmp.push({nx, ny});
            }
            else {
                while(!tmp.empty()) tmp.pop();
                break;
            }
        }
    }
}

void queen(int x, int y, vector <vector<int>> &chess) {
    int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
    int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};
    for(int i=0; i<8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 1 || nx > n || ny < 1 || ny > m) continue; // 벗어남
        if(chess[nx][ny] == 0 || chess[nx][ny] == 4) { // 장애물이 없다면
            tmp.push({nx, ny}); // 다음 위치
            chess[nx][ny] = 4;
            move(dx[i], dy[i], chess);
        }
    }
}

void knight(int x, int y, vector <vector<int>> &chess) {
    int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
    int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
    for(int i=0; i<8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 1 || nx > n || ny < 1 || ny > m) continue; // 벗어남
        if(chess[nx][ny] == 0) {
            chess[nx][ny] = 4;
        }
    }
}

int main() {
    int t = 3, cnt = 0;
    cin >> n >> m; // 체스 행, 열
    vector <vector<int>> chess(n + 1, vector<int>(m + 1, 0)); // 체스판
    for(int block=1; block<=t; block++) {
        int n;
        cin >> n;
        for(int i=0; i<n; i++) {
            int x, y;
            cin >> x >> y;
            chess[x][y] = block;
        }
    }

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(chess[i][j] == 1) {
                queen(i, j, chess);
            }
            if(chess[i][j] == 2) {
                knight(i, j, chess);
            }
        }
    }
   
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(chess[i][j] == 0) {
                cnt++;
            }
        }
    }
   
    cout << cnt;

    return 0;
}

Feedback

---

• 퀸과 나이트의 이동 위치가 같을 경우 문제 발생.
  → 퀸이 이동한 곳을 나이트가 가지 못하도록 구현한 것이 원인이었다.
  +) 체스 경험이 없어서 어려운 것도 있었다 ㅠㅡㅠ