<백준 알고리즘> 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, r(1), c(1), r(2), c(2), ..., r(k), c(k) 이 빈 칸을 사이에 두고 주어진다는 것이다. 여기서 r(i)는 i번째 말의 행 위치, c(i)는 i번째 말의 열 위치를 의미한다. 한 칸에는 하나의 말만 놓인다고 가정한다. Knight, Queen, Pawn의 개수는 각각 100을 넘지 않는 음이 아닌 정수이다.

출력

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

예제 입력 1

4 4 2 1 4 2 4 1 1 2 1 2 3

예제 출력 1

6

예제 입력 2

2 3 1 1 2 1 1 1 0

예제 출력 2

0

---

Solution

#include<stdio.h>
#include<stdlib.h>

int main(void)
{
	int n, m, **chess=NULL, queen_move[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}, knight_move[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}, count, r, c;

	scanf("%d%d", &n, &m);
	chess=(int **)malloc(n*sizeof(int *));
	for(int i=0;i<n;i++)
		chess[i]=(int *)calloc(m,sizeof(int));

	scanf("%d", &count);
	for(int queen=0;queen<count;queen++)
	{
		scanf("%d%d", &r, &c);
		chess[r-1][c-1]=1;
	}

	scanf("%d", &count);
	for(int knight=0;knight<count;knight++)
	{
		scanf("%d%d", &r, &c);
		chess[r-1][c-1]=2;
	}

	scanf("%d", &count);
	for(int pawn=0;pawn<count;pawn++)
	{
		scanf("%d%d", &r, &c);
		chess[r-1][c-1]=3;
	}

	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(chess[i][j]==1)
				for(int k=0;k<8;k++)
				{
					int l=1;

					while(i+l*queen_move[k][0]>=0 && i+l*queen_move[k][0]<n && j+l*queen_move[k][1]>=0 && j+l*queen_move[k][1]<m)
					{
						if(chess[i+l*queen_move[k][0]][j+l*queen_move[k][1]]==0 || chess[i+l*queen_move[k][0]][j+l*queen_move[k][1]]==-1)
							chess[i+l*queen_move[k][0]][j+l*queen_move[k][1]]=-1;
						else
							break;
						l++;
					}
				}
			else if(chess[i][j]==2)
				for(int k=0;k<8;k++)
					if(i+knight_move[k][0]>=0 && i+knight_move[k][0]<n && j+knight_move[k][1]>=0 && j+knight_move[k][1]<m)
						if(chess[i+knight_move[k][0]][j+knight_move[k][1]]==0)
							chess[i+knight_move[k][0]][j+knight_move[k][1]]=-1;

	count=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
			count+=chess[i][j]==0;
		free(chess[i]);
	}
	free(chess);
	printf("%d\n", count);
	return 0;
}

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int count, r, c, queen_move[][]= new int[][] {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}, knight_move[][]=new int[][] {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
		st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		int[][] chess=new int[n][m];
		
		st=new StringTokenizer(br.readLine());
		count=Integer.parseInt(st.nextToken());
		for(int queen=0;queen<count;queen++) {
			r=Integer.parseInt(st.nextToken());
			c=Integer.parseInt(st.nextToken());
			chess[r-1][c-1]=1;
		}
		
		st=new StringTokenizer(br.readLine());
		count=Integer.parseInt(st.nextToken());
		for(int knight=0;knight<count;knight++) {
			r=Integer.parseInt(st.nextToken());
			c=Integer.parseInt(st.nextToken());
			chess[r-1][c-1]=2;
		}

		st=new StringTokenizer(br.readLine());
		count=Integer.parseInt(st.nextToken());
		for(int pawn=0;pawn<count;pawn++) {
			r=Integer.parseInt(st.nextToken());
			c=Integer.parseInt(st.nextToken());
			chess[r-1][c-1]=3;
		}

		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(chess[i][j]==1)
					for(int k=0;k<8;k++) {
						int l=1;
						
						while(i+l*queen_move[k][0]>=0 && i+l*queen_move[k][0]<n && j+l*queen_move[k][1]>=0 && j+l*queen_move[k][1]<m)
						{
							if(chess[i+l*queen_move[k][0]][j+l*queen_move[k][1]]==0 || chess[i+l*queen_move[k][0]][j+l*queen_move[k][1]]==-1)
								chess[i+l*queen_move[k][0]][j+l*queen_move[k][1]]=-1;
							else
								break;
							l++;
						}
					}
				else if(chess[i][j]==2)
					for(int k=0;k<8;k++)
						if(i+knight_move[k][0]>=0 && i+knight_move[k][0]<n && j+knight_move[k][1]>=0 && j+knight_move[k][1]<m)
							if(chess[i+knight_move[k][0]][j+knight_move[k][1]]==0)
								chess[i+knight_move[k][0]][j+knight_move[k][1]]=-1;

		count=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(chess[i][j]==0)
					count++;
		
		System.out.println(count);
	}
}