[BaekJoon/백준] 1986번 체스

 

이 문제는, 학교에서 Week6_2에 풀었던 문제와 비슷하다.

 

1. 퀸을 먼저 위치에 배치( 값 : 1 )
2. 나이트를 위치에 배치 ( 값 : 2)
3. 폰을 위치에 배치 ( 값 : 3 )
4. 퀸의 각 위치에서, 갈 수 있는 위치 계산
5. 나이트의 각 위치에서, 갈 수 있는 위치 계산

 

이 순서로 진행하면 된다.

 

주의할 점은, 4번에서 퀸이 움직일 수 있는 위치 판별에는 값이 2 또는 3을 마주하지 않을 때 이다.

1이라고 해서 멈추면 안된다!!

(https://www.acmicpc.net/board/view/28081)

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;

// Queen : 1, Knight : 2, Pawn : 3
int MAP[1000][1000];

vector<pair<int, int>> Q, K;

// 퀸의 움직임
int mx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int my[8] = {1, -1, 0, 0, 1, -1, 1, -1};


int sx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int sy[8] = {-2, -1, 1, 2, -2, -1, 1, 2};

// 퀸의 움직임 세팅
void Queen_SET() {
    
    
    int Q_S = Q.size();
    
    for(int i = 0; i < Q_S; i++) {
        
        int x = Q[i].first;
        int y = Q[i].second;
        
        int tx, ty;
        
        // 해당 방향 각각으로 쭉 직진
        for(int i = 0; i < 8; i++) {
            
            tx = x + mx[i];
            ty = y + my[i];
            
            while(1) {
                
                // 벗어나면 종료
                if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                    break;
                
                // 장애물 마주쳐도 종료
                if(MAP[tx][ty] == 3 || MAP[tx][ty] == 2)
                    break;
                
                // 아니면 진행
                MAP[tx][ty] = 1;
                tx += mx[i];
                ty += my[i];
                
            }
            
        }
        
    }
            
}

// 나이트의 움직임 세팅
void Knight_SET() {
    
    int K_S = K.size();
    
    for(int i = 0; i < K_S; i++) {
        
        int x = K[i].first;
        int y = K[i].second;
        
        for(int i = 0; i < 8; i++) {
            
            int tx = x + sx[i];
            int ty = y + sy[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                continue;
            
            MAP[tx][ty] = 2;
            
        }
        
    }
}

int main() {
    
    int tC, tX, tY;
    
    cin >> N >> M;
    
    // 퀸
    cin >> tC;
    for(int i = 0; i < tC; i++) {
        cin >> tX >> tY;
        
        MAP[tX - 1][tY - 1] = 1;

        Q.push_back({tX - 1, tY - 1});
    }
    
    // 나이트
    cin >> tC;
    for(int i = 0; i < tC; i++) {
        cin >> tX >> tY;
        
        MAP[tX - 1][tY - 1] = 2;

        K.push_back({tX - 1, tY - 1});
    }
    
    // 폰
    cin >> tC;
    for(int i = 0; i < tC; i++) {
        cin >> tX >> tY;
        
        MAP[tX - 1][tY - 1] = 3;
    }

    
    Queen_SET();
    Knight_SET();
    
    int C = 0;
    
    // 아예 N x M을 초깃값으로 계산해놓고, 배치할때마다 1씩 감소시켜서 계산해왔어도 되고, 이렇게 마지막에 한번에 구해도 되고.
    for(int i = 0; i < N ; i++) {
        for(int j = 0; j < M; j++) {
            if(MAP[i][j] == 0)
                C++;
        }
    }
    
    cout << C << "\n";
}

 

 

소요 시간 : 40분