[Baekjoon] 1986_체스

Silver I

문제(출처: https://www.acmicpc.net/problem/1986)

---

< 체스 >

 

문제 풀이 

 

Queen : 가로, 세로, 대각선 이동

Knight : 2x3 직사각형을 그렸을 때, 반대쪽 꼭짓점 이동 (8칸)

Pawn : 장애물 역할

 

Queen과 Knight이 이동할 수 있는 칸을 찾아 확인한다.

 

 my solution (Java)

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

public class _1986_ { // 체스
	static int arr[][];

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		arr = new int[n][m];
		Queue<int[]> queue = new LinkedList<>();

		st = new StringTokenizer(bf.readLine());
		int num = Integer.parseInt(st.nextToken());
		for (int i = 0; i < num; i++) {
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			queue.add(new int[] { x, y });
			arr[x][y] = 1;
		}

		st = new StringTokenizer(bf.readLine());
		num = Integer.parseInt(st.nextToken());
		for (int i = 0; i < num; i++) {
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			queue.add(new int[] { x, y });
			arr[x][y] = 2;
		}

		st = new StringTokenizer(bf.readLine());
		num = Integer.parseInt(st.nextToken());
		for (int i = 0; i < num; i++) {
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			arr[x][y] = 3;
		}

		move(queue);

		int result = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 0) {
					result += 1;
				}
			}
		}
		System.out.println(result);
	}

	private static void move(Queue<int[]> queue) {
		int dx1[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
		int dy1[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

		int dx2[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
		int dy2[] = { 1, 2, 2, 1, -1, -2, -2, -1 };

		while (!queue.isEmpty()) {
			int info[] = queue.poll();
			if (arr[info[0]][info[1]] == 1) {
				for (int i = 0; i < 8; i++) {
					int x = info[0], y = info[1];
					while (true) {
						x += dx1[i];
						y += dy1[i];
						if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && (arr[x][y] == 0 || arr[x][y]==-1)) {
							arr[x][y] = -1;
						} else {
							break;
						}
					}
				}
			} else {
				for (int i = 0; i < 8; i++) {
					int x = info[0] + dx2[i];
					int y = info[1] + dy2[i];
					if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && (arr[x][y] == 0 || arr[x][y]==-1)) {
						arr[x][y] = -1;
					}
				}
			}
		}
	}
}

변수)
arr : 체스 판 정보
n, m : 체크 판 크기
queue : Queen, Knight 좌표
num : 말 개수
x, y : 말 위치
result : 안전한 칸

 

체스판의 크기 n, m을 입력받는다. Queen과 Knight, Pawn의 좌표를 입력받아 각 위치에 1,2,3으로 표시한다. 이때 Queen과 Knight는 이동할 수 있으므로 queue에 좌표를 저장한다. move함수를 호출하여 말을 이동한다. 체스 판을 탐색하며 안전한 칸 개수를 구해 출력한다.

 

move(말 좌표가 저장된 queue)

dx1, dy1 : Queen이 이동할 수 있는 상하좌우+대각선

dx2, dy2 : Knight가 이동할 수 있는 곳

 

queue가 빌 때까지 다음 과정을 반복한다.

1) queue poll

2) 좌표 값이 1이라면 = Queen

2-1) 8방향으로 계속해서 이동 -> 체스판을 벗어나거나 장애물이 있다면 종료/ 체스판 범위 안이며 이동 가능한 곳이라면 방문 표시

3) 좌표 값이 2라면 = Knight

3-1) 8방향으로 이동 -> 체스판 범위 안이며 이동 가능한 곳이라면 방문 표시

 

* 다른 말로 인하여 이미 지나갈 수 있는 곳이라 확인된 곳이라도 이동 가능

---

---