Coding/알고리즘
[알고리즘 TIL] Q1986(구현)
kangplay
2025. 5. 11. 22:20
문제
https://www.acmicpc.net/problem/1986
트러블 슈팅
1. 배열 인덱스 접근 시 조건 순서 문제
퀸의 위협 영역을 구현할 때, 아래와 같은 코드에서 ArrayIndexOutOfBoundsException이 발생했다.
while (!board[i - count][j].equals("Pawn") && i - count >= 0)여기서 i - count가 음수인 상태에서 배열 접근이 먼저 실행되었기 때문에 런타임 오류가 발생했다. 조건 순서를 반드시 인덱스 유효성 검사 → 배열 접근 순으로 바꿔야 한다.
while (i - count >= 0 && board[i - count][j].equals("Safe")) {
...
}
2. 나이트 이동 구현 중 조건문 반복 → 방향 배열로 리팩토링
나이트의 이동 범위를 다음처럼 8개의 if 문으로 작성했는데, 코드 중복이 심하고 유지보수가 어려웠다.
if (i - 2 > -1 && j - 1 > -1) ...
if (i - 2 > -1 && j + 1 < m) ...
...나이트의 모든 이동 방향을 dx, dy 배열로 선언한 후, 반복문으로 처리하도록 리팩토링했다.
private static final int[][] KNIGHT_MOVES = {
{-2, -1}, {-2, 1}, {2, -1}, {2, 1},
{-1, -2}, {-1, 2}, {1, -2}, {1, 2}
};
for (int[] move : KNIGHT_MOVES) {
int ni = i + move[0];
int nj = j + move[1];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && board[ni][nj].equals("Safe")) {
board[ni][nj] = "Unsafe";
}
}퀸도 다음과 같이 리팩토링할 수 있다.
// 8방향: ↖ ↑ ↗ → ↘ ↓ ↙ ←
int[] dx = {-1, 0, 1, 1, 1, 0, -1, -1};
int[] dy = {-1, -1, -1, 0, 1, 1, 1, 0};
for (int dir = 0; dir < 8; dir++) {
int ny = i, nx = j;
while (true) {
ny += dy[dir];
nx += dx[dir];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) break; // 경계
if (!board[ny][nx].equals("Safe")) break; // 말 or Pawn이 막으면 멈춤
board[ny][nx] = "Unsafe";
}
}-> 시뮬레이션 문제에서 방향이 정해진 이동은 무조건 dx/dy 배열로 추상화하자 !!
구현
import java.io.*;
public class Q1986 {
static BufferedReader br;
static BufferedWriter bw;
static String[][] chessBoard;
static int n, m;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] inputStrArr = br.readLine().split(" ");
n = Integer.parseInt(inputStrArr[0]);
m = Integer.parseInt(inputStrArr[1]);
chessBoard = new String[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
chessBoard[i][j] = "Safe";
}
}
getChessPiecesData("Queen");
getChessPiecesData("Knight");
getChessPiecesData("Pawn");
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
String chess = chessBoard[i][j];
switch (chess) {
case "Queen":
checkUnSafeByQueen(i, j);
break;
case "Knight":
checkUnSafeByKnight(i, j);
break;
}
}
}
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (chessBoard[i][j].equals("Safe")) result++;
}
}
bw.write(result+"");
bw.flush();
bw.close();
br.close();
}
private static void checkUnSafeByKnight(int i, int j) {
if (i - 2 > -1 && j - 1 > -1 && chessBoard[i - 2][j - 1].equals("Safe")) chessBoard[i - 2][j - 1] = "Unsafe";
if (i - 2 > -1 && j + 1 < m && chessBoard[i - 2][j + 1].equals("Safe")) chessBoard[i - 2][j + 1] = "Unsafe";
if (i + 2 < n && j - 1 > -1 && chessBoard[i + 2][j - 1].equals("Safe")) chessBoard[i + 2][j - 1] = "Unsafe";
if (i + 2 < n && j + 1 < m && chessBoard[i + 2][j + 1].equals("Safe")) chessBoard[i + 2][j + 1] = "Unsafe";
if (i - 1 > -1 && j - 2 > -1 && chessBoard[i - 1][j - 2].equals("Safe")) chessBoard[i - 1][j - 2] = "Unsafe";
if (i - 1 > -1 && j + 2 < m && chessBoard[i - 1][j + 2].equals("Safe")) chessBoard[i - 1][j + 2] = "Unsafe";
if (i + 1 < n && j - 2 > -1 && chessBoard[i + 1][j - 2].equals("Safe")) chessBoard[i + 1][j - 2] = "Unsafe";
if (i + 1 < n && j + 2 < m && chessBoard[i + 1][j + 2].equals("Safe")) chessBoard[i + 1][j + 2] = "Unsafe";
}
private static void checkUnSafeByQueen(int i, int j) {
int count = 1;
while (i - count > -1 && !(chessBoard[i - count][j].equals("Queen") || chessBoard[i - count][j].equals("Knight") || chessBoard[i - count][j].equals("Pawn"))) {
chessBoard[i - count][j] = "Unsafe";
count++;
}
count = 1;
while ( i + count < n && !(chessBoard[i + count][j].equals("Queen") || chessBoard[i + count][j].equals("Knight") || chessBoard[i + count][j].equals("Pawn"))) {
chessBoard[i + count][j] = "Unsafe";
count++;
}
count = 1;
while (j - count > -1 && !(chessBoard[i][j - count].equals("Queen") || chessBoard[i][j - count].equals("Knight") || chessBoard[i][j - count].equals("Pawn"))) {
chessBoard[i][j - count] = "Unsafe";
count++;
}
count = 1;
while (j + count < m && !(chessBoard[i][j + count].equals("Queen") || chessBoard[i][j + count].equals("Knight") || chessBoard[i][j + count].equals("Pawn"))) {
chessBoard[i][j + count] = "Unsafe";
count++;
}
count = 1;
while (i - count > -1 && j - count > -1 && !(chessBoard[i - count][j - count].equals("Queen") || chessBoard[i - count][j - count].equals("Knight") || chessBoard[i - count][j - count].equals("Pawn"))) {
chessBoard[i - count][j - count] = "Unsafe";
count++;
}
count = 1;
while (i + count < n && j + count < m && !(chessBoard[i + count][j + count].equals("Queen") || chessBoard[i + count][j + count].equals("Knight") || chessBoard[i + count][j + count].equals("Pawn"))) {
chessBoard[i + count][j + count] = "Unsafe";
count++;
}
count = 1;
while (i - count > -1 && j + count <m && !(chessBoard[i - count][j + count].equals("Queen") || chessBoard[i - count][j + count].equals("Knight") || chessBoard[i - count][j + count].equals("Pawn"))) {
chessBoard[i - count][j + count] = "Unsafe";
count++;
}
count = 1;
while (i + count < n && j - count >-1 && !(chessBoard[i + count][j - count].equals("Queen") || chessBoard[i + count][j - count].equals("Knight") || chessBoard[i + count][j - count].equals("Pawn"))) {
chessBoard[i + count][j - count] = "Unsafe";
count++;
}
}
private static void getChessPiecesData(String pieceName) throws IOException {
String[] inputStrArr = br.readLine().split(" ");
int count = Integer.parseInt(inputStrArr[0]);
for (int i = 0; i < count; i++) {
int row = Integer.parseInt(inputStrArr[i * 2 + 1]) - 1;
int col = Integer.parseInt(inputStrArr[i * 2 + 2]) - 1;
chessBoard[row][col] = pieceName;
}
}
}