BaekJoon 1986번: 체스(C++)

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

1986번: 체스

풀이법

1) 구현 문제였으며, 배열의 크기가 1000x1000일 수 있기에 최대한 적은 for문과 많은 if문으로 문제를 해결하였다. 

2) 입력을 받으며 탐색을 진행하기에는 pawn 혹은 다른 말들이 장애물이 될 수 있기에 모두 입력을 받고 count를 실시했다.

3) knight의 경우 장애물이 있어도 갈 수 있는 경우가 총 8개 이므로 이를 배열로 만들고 순환하며 갈 수 있는 공간을 count해 주었다.

4) queen의 경우 상/하/좌/우/좌상/좌하/우상/우하 방향이 가능하기에 모두 고려해 주었으며 해당 방향으로 나아갈 수 있는지 범위를 상세히 설정하였고, 막힌 경우 그 방향은 더 이상 탐색하지 않았다.

5) 한 번 방문한 곳을 visited배열에 담아서 count 시에 활용하였다. knight가 한 번 방문한 곳이더라도, queen이 해당 배열을 방문하는 경우 count 시키지 않았으나 막히지는 않았기에, 해당 방향으로 탐색은 계속하도록 코딩을 진행하였다.

 

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#define INF 987654321
using namespace std;

int n, m;
int arr[1001][1001];
bool visited[1001][1001];
int knightNum, queenNum, pawnNum;
int vx[8] = { -2,-2,-1,1,2,2,1,-1 };
int vy[8] = { -1,1,2,2,1,-1,-2,-2 };

vector<pair<int, int>> qPair;
vector<pair<int, int>> kPair;
int cnt = 0;
void checkKnight()
{
	for (int p = 0; p < kPair.size(); p++)
	{
		int nowX = kPair[p].first;
		int nowY = kPair[p].second;
		for (int i = 0; i < 8; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX<1 || nextY<1 || nextX>n || nextY>m)
				continue;
			if (!visited[nextX][nextY] && arr[nextX][nextY]==0)
			{
				visited[nextX][nextY] = true;
				cnt++;
			}
		}
	}
}
void checkQueen()
{
	for (int p = 0; p < qPair.size(); p++)
	{
		int nowX = qPair[p].first;
		int nowY = qPair[p].second;
		//상하좌우
		for (int i = nowX-1; i >= 1; i--)//상
		{
			if (arr[i][nowY] == 0)
			{
				if (!visited[i][nowY])
				{
					visited[i][nowY] = true;
					cnt++;
				}
			}
			else
				break;
		}
		for (int i = nowX+1; i <=n; i++)//하
		{
			if (arr[i][nowY] == 0)
			{
				if (!visited[i][nowY])
				{
					visited[i][nowY] = true;
					cnt++;
				}
			}
			else
				break;
		}
		for (int i = nowY - 1; i >= 1; i--)//좌
		{
			if (arr[nowX][i] == 0)
			{
				if (!visited[nowX][i])
				{
					visited[nowX][i] = true;
					cnt++;
				}
			}
			else
				break;
		}
		for (int i = nowY + 1; i <=m; i++)//우
		{
			if (arr[nowX][i] == 0)
			{
				if (!visited[nowX][i])
				{
					visited[nowX][i] = true;
					cnt++;
				}
			}
			else
				break;
		}
		bool LU = true;
		bool RU = true;
		bool LD = true;
		bool RD = true;
		int repeat = max(n, m);
		for (int i = 1;i<=repeat; i++)
		{
			int nextLUX = nowX - i; // 좌상
			int nextLUY = nowY - i;
			int nextRUX = nowX -i;
			int nextRUY = nowY + i;//우상
			int nextLDX = nowX + i;//좌하
			int nextLDY = nowY - i;
			int nextRDX = nowX + i;//우하
			int nextRDY = nowY + i;
			if (LU == true &&nextLUX >= 1 && nextLUY >=1)
			{
				if (arr[nextLUX][nextLUY]==0)
				{
					if (!visited[nextLUX][nextLUY])
					{
						visited[nextLUX][nextLUY] = true;
						cnt++;
					}
				}
				else
				{
					LU = false;
				}
			}
			if (RU == true&& nextRUX >= 1 && nextRUY <= m)
			{
				if (arr[nextRUX][nextRUY] == 0)
				{
					if (!visited[nextRUX][nextRUY])
					{
						visited[nextRUX][nextRUY] = true;
						cnt++;
					}
				}
				else
				{
					RU = false;
				}
			}
			if (LD == true&&nextLDX <= n && nextLDY >= 1)
			{
				if (arr[nextLDX][nextLDY] == 0)
				{
					if (!visited[nextLDX][nextLDY])
					{
						visited[nextLDX][nextLDY] = true;
						cnt++;
					}
				}
				else
				{
					LD = false;
				}
			}
			if (RD == true&&nextRDX <= n && nextRDY <= m)
			{
				if (arr[nextRDX][nextRDY] == 0)
				{
					if (!visited[nextRDX][nextRDY])
					{
						visited[nextRDX][nextRDY] = true;
						cnt++;
					}
				}
				else
				{
					RD = false;
				}
			}
			

		}
		//대각선

	}
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;

	cin >> queenNum;
	for (int i = 0; i < queenNum; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;//queen
		qPair.push_back({ a,b });
		cnt++;
	}
	cin >> knightNum;
	for (int i = 0; i < knightNum; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a][b] = 2;//knight;
		kPair.push_back({ a,b });
		cnt++;
	}
	cin >> pawnNum;
	for (int i = 0; i < pawnNum; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a][b] = 3;
		cnt++;
	}
	checkKnight();
	checkQueen();
	cout << m*n-cnt;
}