[백준 C++] 1986 체스

문제

n×m 크기의 체스 판과, 상대팀의 Queen, Knight, Pawn의 위치가 주어져 있을 때, 안전한 칸이 몇 칸인지 세는 프로그램을 작성하시오. (안전한 칸이란 말은 그 곳에 자신의 말이 있어도 잡힐 가능성이 없다는 것이다.)

참고로 Queen은 가로, 세로, 대각선으로 갈 수 있는 만큼 최대한 많이 이동을 할 수 있는데 만약 그 중간에 장애물이 있다면 이동을 할 수 없다. 그리고 Knight는 2×3 직사각형을 그렸을 때, 반대쪽 꼭짓점으로 이동을 할 수 있다. 아래 그림과 같은 8칸이 이에 해당한다.

이때 Knight는 중간에 장애물이 있더라도 이동을 할 수 있다. 그리고 Pawn은 상대팀의 말은 잡을 수 없다고 하자(즉, 장애물의 역할만 한다는 것이다).

예를 들어 다음과 같이 말이 배치가 되어 있다면 진하게 표시된 부분이 안전한 칸이 될 것이다. (K : Knight, Q : Queen, P : Pawn)

입력

첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1 ≤ n, m ≤ 1000) 그리고 둘째 줄에는 Queen의 개수와 그 개수만큼의 Queen의 위치가 입력된다. 그리고 마찬가지로 셋째 줄에는 Knight의 개수와 위치, 넷째 줄에는 Pawn의 개수와 위치가 입력된다. 즉 둘째 줄, 셋째 줄, 넷째 줄은 k, r1, c1, r2, c2, ..., rk, ck 이 빈 칸을 사이에 두고 주어진다는 것이다. 여기서 ri는 i번째 말의 행 위치, ci는 i번째 말의 열 위치를 의미한다. 한 칸에는 하나의 말만 놓인다고 가정한다. Knight, Queen, Pawn의 개수는 각각 100을 넘지 않는 음이 아닌 정수이다.

출력

첫째 줄에 n×m 체스판에 안전한 칸이 몇 칸인지 출력하시오.

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

풀이

1. 3개의 장애물이 있다.(퀸, 나이트 폰)
2. 퀸은 가로, 세로, 대각선으로 장애물을 만나기전까지 이동가능
3. 나이트만이 장애믈을 무시하고 나이트기준 2,3사각형으로 만들어지는 8개의 꼭짓점까지 한번에 이동가능
4. 모든 이동가능한 경우의수에서 배제된 이동불가능한 지형이 안전한위치고, 이 위치의 갯수를 구해야한다.

1. 입력받는 부분
   
   
   
2. 맵에 체스말을 기록하는 부분
   
   
   map은 실제 장애물들의 위치, res는 안전한곳의 위치
   
   
3. 퀸이 이동하는 경우
   
   모든 퀸의 좌표를 탐색한다.
   3-1. 가로, 세로 방향으로 퀸이 이동하는 경우
   
   장애물이 놓여있지않다면 계속반복하며, 해당위치를 res에 안전하지않은곳으로 표기한다.
   3-2. 대각선으로 퀸이 이동하는경우
   
   
   gap을 +1 씩하며 대각선방향으로 좌표를 확인하되, 유효한 인덱스인지 확인해주었다.
   당연히 결과값은 res에 안전하지않음으로 false로 표기
   
   
4. 나이트가 이동하는 경우
   
   나이트하나가 총 8군데 이동가능하며, 장애물상관없으니 모두 절댓값으로 넣었고, 유효한 인덱스인지만 체크해주었다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector;
using std::pair;
vector<pair<int, int>> queen, knight, pawn;
int n, m, qn, kn, pn, **map; //map: 입력받은 체스말 위치 기록
bool** res; //안전한곳인지 check

int printAll() {
	int cnt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (res[i][j])
				cnt++;
	return cnt;
}

void make_map() {
	//맵 선언과 초기화
	map = new int* [n];
	res = new bool* [n];
	for (int i = 0; i < n; i++) {
		map[i] = new int[m];
		res[i] = new bool[m];
		for (int j = 0; j < m; j++) {
			map[i][j] = 0; // 처음엔 모두 빈공간으로 기록
			res[i][j] = true; //처음엔 모두 안전한곳으로 기록
		}
	}

	//queen위치 => 1 기록
	for (int i = 0; i < qn; i++) {
		int x = queen[i].first, y = queen[i].second;
		map[x][y] = 1;
		res[x][y] = false;
	}
	//knight위치 => 2 기록
	for (int i = 0; i < kn; i++) {
		int x = knight[i].first, y = knight[i].second;
		map[x][y] = 2;
		res[x][y] = false;
	}
	//pawn위치 => 3 기록
	for (int i = 0; i < pn; i++) {
		int x = pawn[i].first, y = pawn[i].second;
		map[x][y] = 3;
		res[x][y] = false;
	}
}

void queen_check() { //장애물 상관 O
	for (int k = 0; k < qn; k++) { //퀸갯수만큼반복
		int x = queen[k].first, y = queen[k].second; //현재퀸의 좌표
		
		//← 탐색
		for (int i = y - 1; i >= 0; i--) {
			if (map[x][i] != 0) //장애물만날시 스탑
				break;
			res[x][i] = false; //퀸이 이동가능하므로 안전하지않은곳
		}
		//→ 탐색
		for (int i = y + 1; i < m; i++) {
			if (map[x][i] != 0) 
				break;
			res[x][i] = false; 
		}
		//↑ 탐색
		for (int i = x - 1; i >= 0; i--) {
			if (map[i][y] != 0)
				break;
			res[i][y] = false;
		}
		//↓ 탐색
		for (int i = x + 1; i < n; i++) {
			if (map[i][y] != 0)
				break;
			res[i][y] = false;
		}
		
		//↖ 탐색
		for (int gap = 1; ; gap++) {
			if (x - gap <= -1 || y - gap <= -1) //범위를 벗어난경우 스탑
				break;
			if (map[x - gap][y - gap] != 0) //다른 체스말이 놓인경우 스탑
				break;
			res[x - gap][y - gap] = false;
		}
		//↘ 탐색
		for (int gap = 1; ; gap++) {
			if (x + gap >= n || y + gap >= m) 
				break;
			if (map[x + gap][y + gap] != 0) 
				break;
			res[x + gap][y + gap] = false;
		}
		//↗ 탐색
		for (int gap = 1; ; gap++) {
			if (x - gap < 0 || y + gap >= m) 
				break;
			if (map[x - gap][y + gap] != 0) 
				break;
			res[x - gap][y + gap] = false;
		}
		//↙ 탐색
		for (int gap = 1; ; gap++) {
			if (x + gap >= n || y - gap < 0) 
				break;
			if (map[x + gap][y - gap] != 0) 
				break;
			res[x + gap][y - gap] = false;
		}
	}
}

void knight_check() { //장애물 상관 X
	for (int k = 0; k < kn; k++) {
		int x = knight[k].first, y = knight[k].second;
		//←↖ 
		if (x - 1 >= 0 && y - 2 >= 0)
			res[x - 1][y - 2] = false;
		//↑↖ 
		if (x - 2 >= 0 && y - 1 >= 0)
			res[x - 2][y - 1] = false;
		//↗↑ 
		if (x - 2 >= 0 && y + 1 < m)
			res[x - 2][y + 1] = false;
		//↗→ 
		if (x - 1 >= 0 && y + 2 < m)
			res[x - 1][y + 2] = false;
		//↘→
		if (x + 1 < n && y + 2 < m)
			res[x + 1][y + 2] = false;
		//↘↓
		if (x + 2 < n && y + 1 < m)
			res[x + 2][y + 1] = false;
		//↓↙
		if (x + 2 < n && y - 1 < m)
			res[x + 2][y - 1] = false;
		//←↙
		if (x + 1 < n && y - 2 < m)
			res[x + 1][y - 2] = false;
	}
}

int main(void) {
	scanf("%d %d", &n, &m); 
	scanf("%d", &qn); //퀸입력
	for (int i = 0, x, y; i < qn; i++) {
		scanf("%d %d", &x, &y);
		queen.push_back({ x-1, y-1 }); //인덱스로 계산하기위해 -1씩
	}
	scanf("%d", &kn); //나이트입력
	for (int i = 0, x, y; i < kn; i++) {
		scanf("%d %d", &x, &y);
		knight.push_back({ x-1, y-1 });
	}
	scanf("%d", &pn); //폰입력
	for (int i = 0, x, y; i < pn; i++) {
		scanf("%d %d", &x, &y);
		pawn.push_back({ x-1, y-1 });
	}

	make_map();
	queen_check();
	knight_check();

	printf("%d", printAll()); //출력

	return 0;
}