백준 1986 체스 C++

https://www.acmicpc.net/problem/1986

1986번: 체스

1. 시작  

 이 문제는 구현 문제로 체스판의 크기, 퀸, 나이트, 폰의 개수와 각각의 위치가 주어졌을 때 안전한 칸의 개수는 얼마인지 출력하는 문제이다. 특별히 고려할 점이 없고 그냥 주어진 퀸, 나이트의 이동 가능 범위와 각 기물들의 위치를 고려하기만 하면 되는 문제이다.

---

2. 해결 과정

전술하였듯, 고려해야 할 것은 각 기물들의 위치와 이동 범위이다. 따라서, 고려한 해결 과정은 다음과 같다.

1. 체스판의 위치를 입력 받는다.
2. 퀸의 개수와 각 퀸의 위치를 입력 받는다. 그리고 이 때, 기물의 위치를 기록하는 2차원 배열 piece를 이용해 각 퀸의 위치를 기록하고, 안전하지 않다는 것도 기록한다.
3. 나이트 역시 퀸과 마찬가지로 개수와 위치를 입력받는다. 그리고 이것들의 위치 역시 기록한다.
4. 폰의 개수와 위치를 입력받는다. 
5. 입력받은 각 퀸의 위치를 통해 모든 퀸의 이동 범위를 조사한다. 그리고 퀸이 이동할 수 있는 곳이라면 그 곳은 안전하지 않다고 기록한다. 이 때, 이동 범위에 다른 기물이 있다면 그 방향으로의 이동을 그만둔다.
6. 나이트 역시 마찬가지로 각 이동 범위를 조사하여 그 곳이 안전하지 않은지 검사한다.
7. 모든 기물들의 이동 범위를 조사하였다면 체스판의 모든 위치를 하나 하나 안전한지 아닌지 체크한다. 그리고 답을 출력한다.

 여기서 각 체스판의 위치가 안전한지 아닌지는 bool isSafe[MAX][MAX]를 통해 기록하였다, 만약 isSafe[3][2]가 true라면 (3, 2)는 안전하다는 뜻이며 isSafe[3][2]가 false라면 안전하지 않다는 뜻이다. 또헌 기물의 위치는 bool piece[MAX][MAX]를 이용해 기록하였다. isSafe와 piece를 별도로 선언한 이유는, 변수를 하나만 이용해서는 현재 역량으로는 다른 기물에 의한 이동 제한을 구현할 수 없었기 때문이다. 그리고 폰의 이동 범위를 따로 언급하지 않았는데, 이는 문제에서 폰은 그저 장애물 역할을 한다고 하였기 때문이다.

---

3. 코드

위의 과정을 구현한 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#pragma warning(disable:4996)

using namespace std;

#define MAX 1001

int R, C;
int queenNum, knightNum, pawnNum;
bool isSafe[MAX][MAX];
bool piece[MAX][MAX];
vector<pair<int, int>> queens;
vector<pair<int, int>> knights;
int nxtQueenR[8] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int nxtQueenC[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int knightR[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int knightC[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };

bool IsIn(int r, int c)
{
	return 1 <= r && r <= R && 1 <= c && c <= C;
}

void QueenCheck()
{
	for (int q = 0; q < queens.size(); ++q)
	{
		int qr = queens[q].first;
		int qc = queens[q].second;

		for (int i = 0; i < 8; ++i)
		{
			int nxtR = qr + nxtQueenR[i];
			int nxtC = qc + nxtQueenC[i];

			while(IsIn(nxtR, nxtC) && piece[nxtR][nxtC] == false)
			{
				isSafe[nxtR][nxtC] = false;
	
				nxtR += nxtQueenR[i];
				nxtC += nxtQueenC[i];
			}
		}
	}
}

void KnightCheck()
{
	for (int k = 0; k < knights.size(); ++k)
	{
		int kr = knights[k].first;
		int kc = knights[k].second;

		for (int i = 0; i < 8; ++i)
		{
			int nxtKnightR = kr + knightR[i];
			int nxtKnightC = kc + knightC[i];

			if (IsIn(nxtKnightR, nxtKnightC))
			{
				if (piece[nxtKnightR][nxtKnightC] == false)
					isSafe[nxtKnightR][nxtKnightC] = false;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	memset(isSafe, true, sizeof(isSafe));

	cin >> R >> C;

	cin >> queenNum;
	for (int i = 0; i < queenNum; ++i)
	{
		int r, c;
		cin >> r >> c;

		queens.push_back({ r, c });
		isSafe[r][c] = false;
		piece[r][c] = true;
	}

	cin >> knightNum; 
	for (int i = 0; i < knightNum; ++i)
	{
		int r, c;
		cin >> r >> c;

		knights.push_back({ r, c });
		isSafe[r][c] = false;
		piece[r][c] = true;
	}

	cin >> pawnNum;
	for (int i = 0; i < pawnNum; ++i)
	{
		int r, c;
		cin >> r >> c;

		isSafe[r][c] = false;
		piece[r][c] = true;
	}
	
	QueenCheck();
	KnightCheck();

	int answer = R * C;

	for (int r = 1; r <= R; ++r)
	{
		for (int c = 1; c <= C; ++c)
		{
			if (isSafe[r][c] == false)
				--answer;
		}
	}

	cout << answer << endl;

	return 0;
}

 퀸의 이동 방향(nxtQueenR, nxtQueenC)는 인덱스 0번부터 북서쪽, 북쪽, 북동쪽, 동쪽, 남동쪽, 남쪽, 남서쪽, 서쪽이다.