2019-03-21 [JAVA]백준 1986번 - 체스
22 Mar 2019 | java algorithm_study백준 1986 : 체스
문제출처
https://www.acmicpc.net/problem/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 체스판에 안전한 칸이 몇 칸인지 출력하시오.
예제 입력 1 복사
4 4
2 1 4 2 4
1 1 2
1 2 3
문제 풀이
-
체스판에서 Queen, Knight, Pawn의 위치를 지정
-
Queen과 Knight 이동
- Queen
-
자기 위치를 기준으로 상하좌우 대각선으로 직진 (장애물이 있을시 이동 중단)1
-
Queen의 위치를 0,0 이라 가정하여 x, y좌표로 나누어 배열로 선언
static int[] Queen_X = {-1, -1, 0, 1, 1, 1, 0, -1}; static int[] Queen_Y = {0, 1, 1, 1, 0, -1, -1, -1}- Queen가 이동할수 있으면 -1
public static void Queen(int x, int y) { for (int i = 0; i < 8; i++) { int queenX = x + Queen_X[i]; int queenY = y + Queen_Y[i]; while (queenX >= 0 && queenX < M && queenY < N && queenY >= 0 && chessBoard[queenY][queenX] <= 0) { chessBoard[queenY][queenX] = -1;//Queen 이동 경로 체크 queenX += Queen_X[i]; queenY += Queen_Y[i]; } } } -
-
Knight
-
자기 위치를 기준으로 2*3직사각형을 그려 반대쪽 꼭짓점
-
Knight의 위치를 0,0 이라 가정하여 x, y좌표로 나누어 배열로 선언
static int[] Knight_X = {-2, -1, 1, 2, 2, 1, -1, -2}; static int[] Knight_Y = {1, 2, 2, 1, -1, -2, -2, -1}; -
Knight가 이동할수 있으면 -1
public static void Knight(int x, int y) { for (int i = 0; i < 8; i++) { int knightX = x + Knight_X[i]; int knightY = y + Knight_Y[i]; if (knightX >= 0 && knightX < M && knightY < N && knightY >= 0) if (chessBoard[knightY][knightX] == 0)//Knight 이동 경로 체크 chessBoard[knightY][knightX] = -1; } } -
- Queen
-
안전한 칸 개수 세기
for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (chessBoard[i][j] == 0)//체스판이 0이면 Knight나 Queen의 이동 경로에 없다. count++;
전체 소스
import java.util.Scanner;
public class Baekjoon_1986 {
static int[] Knight_X = {-2, -1, 1, 2, 2, 1, -1, -2};
static int[] Knight_Y = {1, 2, 2, 1, -1, -2, -2, -1};
static int[] Queen_X = {-1, -1, 0, 1, 1, 1, 0, -1};
static int[] Queen_Y = {0, 1, 1, 1, 0, -1, -1, -1};
static int N, M;
static int[][] chessBoard;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
int count = 0;
chessBoard = new int[N][M]; // 체스판 1: queen 2: knight 3: pawn 위치
int k = sc.nextInt();
for (int i = 0; i < k; i++)
chessBoard[sc.nextInt() - 1][sc.nextInt() - 1] = 1;
k = sc.nextInt();
for (int i = 0; i < k; i++)
chessBoard[sc.nextInt() - 1][sc.nextInt() - 1] = 2;
k = sc.nextInt();
for (int i = 0; i < k; i++)
chessBoard[sc.nextInt() - 1][sc.nextInt() - 1] = 3;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (chessBoard[i][j] == 1)
Queen(j, i);
else if (chessBoard[i][j] == 2)
Knight(j, i);
}
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (chessBoard[i][j] == 0) //체스판이 0이면 Knight나 Queen의 이동 경로에 없다.
count++;
System.out.println(count);
}
public static void Knight(int x, int y) {
for (int i = 0; i < 8; i++) {
int knightX = x + Knight_X[i];
int knightY = y + Knight_Y[i];
if (knightX >= 0 && knightX < M && knightY < N && knightY >= 0)
if (chessBoard[knightY][knightX] == 0) //Knight 이동 경로 체크
chessBoard[knightY][knightX] = -1;
}
}
public static void Queen(int x, int y) {
for (int i = 0; i < 8; i++) {
int queenX = x + Queen_X[i];
int queenY = y + Queen_Y[i];
while (queenX >= 0 && queenX < M && queenY < N && queenY >= 0 && chessBoard[queenY][queenX] <= 0) {
chessBoard[queenY][queenX] = -1; //Queen 이동 경로 체크
queenX += Queen_X[i];
queenY += Queen_Y[i];
}
}
}
}
Comments