[ 백준 1986 ] 체스 (C++)

백준의 체스(1986) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 주어진 맵에 Knight, Queen, Pawn의 위치가 주어졌을 때, 안전한 칸이 총 몇개인지 찾아야 하는 문제이다.

   Knight는 문제에 나와있는 대로 8칸을 움직일 수 있고, Queen은 가로, 세로, 대각선으로 어디든지 나아갈 수 있지만

   중간에 방해물이 있다면 더 이상 나아가지는 못한다. Pawn은 이 문제에서는 방해물의 역할만 한다.

   본인은 먼저 입력으로 주어지는 K,Q,P의 위치를 맵에서 1, 2, 3 으로 저장해 주었다.

   즉, 맵의 상태를 표시하는 MAP[][] 2차원 배열을 하나 사용하였고, 안전 영역을 저장하기 위해서 State[][] 라는 bool형

   2차원 배열을 사용해주었다. State[a][b] = true의 의미는 "(a, b)는 이미 점령당한 좌표이므로 안전영역이 아니다" 라는

   의미이다.

  

2) 본인은, 맵을 입력받은 후에, Knight와 Queen이 갈 수 있는 모든 곳들을 탐색하면서 State[][] 배열의 상태를 true로 바꿔주었다.

   사실, 이 과정은 Knight와 Queen의 움직임만 제대로 이해했다면 어렵지 않은 부분이고, 소스코드만 참고하더라도 알 수 있으

   므로 구체적인 설명은 생략하겠다.

 

   이후, 마지막으로 맵 전체를 돌면서 State[][] 배열의 상태가 false인 좌표들의 갯수를 Count해서 정답으로 출력해주었다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 1001
using namespace std;
 
int N, M;
int Queen_Num, Knight_Num, Pawn_Num;
int MAP[MAX][MAX];
bool State[MAX][MAX];
 
int Q_dx[] = { 0, 0, 1, -1, -1, -1, 1, 1 };
int Q_dy[] = { 1, -1, 0, 0, -1, 1, -1, 1 };
 
int K_dx[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int K_dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
 
void Input()
{
    cin >> N >> M;
    cin >> Queen_Num;
    for (int i = 0; i < Queen_Num; i++)
    {
        int a, b;
        cin >> a >> b;
        MAP[a][b] = 1;    // Queen = 1로 표현
    }
 
    cin >> Knight_Num;
    for (int i = 0; i < Knight_Num; i++)
    {
        int a, b;
        cin >> a >> b;
        MAP[a][b] = 2;    // Knight = 2로 표현
    }
    
    cin >> Pawn_Num;
    for (int i = 0; i < Pawn_Num; i++)
    {
        int a, b; 
        cin >> a >> b;
        MAP[a][b] = 3;    // Pawn = 3으로 표현
    }
}
 
void State_Of_MAP(int x, int y, char C)
{
    if (C == 'Q')
    {
        for (int i = 0; i < 8; i++)
        {
            int nx = x + Q_dx[i];
            int ny = y + Q_dy[i];
 
            while (1)
            {
                if (nx < 1 || ny < 1 || nx > N || ny > M) break;
                if (MAP[nx][ny] != 0) break;
 
                State[nx][ny] = true;
                nx = nx + Q_dx[i];
                ny = ny + Q_dy[i];
            }
        }
    }
    else if (C == 'K')
    {
        for (int i = 0; i < 8; i++)
        {
            int nx = x + K_dx[i];
            int ny = y + K_dy[i];
 
            if (nx >= 1 && ny >= 1 && nx <= N && ny <= M)
            {
                if (MAP[nx][ny] == 0) State[nx][ny] = true;
            }
        }
    }
}
 
void Print()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (State[i][j] == true) cout << 1 << " ";
            else cout << 0 << " ";
        }
        cout << endl;
    }
}
 
void Make_MAP_State()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (MAP[i][j] == 0) continue;
            
            if (MAP[i][j] == 1)
            {
                State[i][j] = true;
                State_Of_MAP(i, j, 'Q');
            }
            else if (MAP[i][j] == 2)
            {
                State[i][j] = true;
                State_Of_MAP(i, j, 'K');
            }
            else if (MAP[i][j] == 3)
            {
                State[i][j] = true;
            }
        }
    }
}
 
int Check_Safe_Area()
{
    int Cnt = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (MAP[i][j] == 0 && State[i][j] == false) Cnt++;
        }
    }
    return Cnt;
}
 
void Solution()
{
    Make_MAP_State();
    cout << Check_Safe_Area() << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}