문제
내가 생각했을때 문제에서 원하는부분
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다.
둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다.
0은 빈 칸, 1은 적이 있는 칸이다.
첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.내가 이 문제를 보고 생각해본 부분
입력 처리 및 초기화
N, M, D를 입력받아 게임판 크기와 궁수 공격 범위를 정한다.
board 배열에 적의 위치를 입력받아 저장한다.
궁수 배치 조합 탐색
3명의 궁수를 성 바로 앞 행(가상의 N+1 행)에 위치시키는데, 가능한 모든 조합(열 위치 3개 선택)을 중첩 반복문으로 생성한다.
각 조합에 대해 시뮬레이션을 수행해 해당 배치로 제거할 수 있는 적의 수를 계산한다.
best 변수에 최대 제거 수를 갱신한다.
게임 시뮬레이션(simulate 메서드)
현재 배치된 궁수 위치에서 게임을 시작한다.
원본 board 데이터를 보존하기 위해 배열을 깊은 복사한다.
최대 N턴 동안 반복하며 각 턴마다 다음을 수행한다.
각 턴의 처리
궁수 3명이 공격할 적을 찾는다.
각 궁수는 맨해튼 거리 |r1 - r2| + |c1 - c2|가 D 이내인 적들을 탐색한다.
가장 가까운 적(거리 우선, 같으면 가장 왼쪽 적)을 선택한다.
여러 궁수가 같은 적을 공격할 수 있지만 중복 제거를 위해 willBeKilled 2차원 배열을 써서 한 번만 카운트한다.
공격 대상 적들을 한꺼번에 제거하며 제거 수를 누적한다.
적 이동 처리
모든 적이 한 칸 아래로 이동한다.
성 바로 앞 행(N행)까지 내려온 적은 제거된다.
배열을 아래에서 위로 복사함으로써 적이 겹치지 않고 이동 가능하다.
최상단 행은 빈 칸으로 초기화한다.
게임 종료 조건 검사
이동 후 적이 하나도 남지 않았다면 시뮬레이션을 종료한다.
최종 결과
모든 궁수 배치 경우의 수에서 제거한 적 수 최대값을 출력한다.코드로 구현
package baekjoon.baekjoon_33;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// 백준 17135번 문제
public class Main1341 {
static int N, M, D;
static int[][] board;
static int best = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
board = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
// 궁수 3명 배치 (조합)
for (int a = 0; a < M - 2; a++) {
for (int b = a + 1; b < M - 1; b++) {
for (int c = b + 1; c < M; c++) {
int killed = simulate(new int[] {a, b, c});
if (killed > best)
best = killed;
}
}
}
System.out.println(best);
br.close();
}
// 주어진 궁수 위치로 시뮬레이션 수행
static int simulate(int[] archers) {
// 맵 복사
int[][] map = new int[N][M];
for (int i = 0; i < N; i++) System.arraycopy(board[i], 0, map[i], 0, M);
int totalKilled = 0;
// 적이 모두 사라지거나 N번 턴(모든 적이 성으로 내려감)까지 반복
for (int turn = 0; turn < N; turn++) {
// 이번 턴에 제거할 적들의 좌표를 저장 (중복 제거 위해 boolean 표시 또는 리스트 + 중복 체크)
boolean[][] willBeKilled = new boolean[N][M];
int killsThisTurn = 0;
// 각 궁수에 대해 표적 찾기
for (int archerCol : archers) {
int targetR = -1, targetC = -1;
int minDist = Integer.MAX_VALUE;
// 모든 적을 검사해서 거리와 조건에 따라 후보 갱신
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
if (map[r][c] == 1) {
int dist = Math.abs(N - r) + Math.abs(archerCol - c); // 궁수는 (N, archerCol)
if (dist <= D) {
if (dist < minDist) {
minDist = dist;
targetR = r;
targetC = c;
} else if (dist == minDist) {
// 거리가 같으면 왼쪽 우선 => 열이 작은 것 선택
if (targetC == -1 || c < targetC) {
targetR = r;
targetC = c;
}
}
}
}
}
}
if (targetR != -1) {
if (!willBeKilled[targetR][targetC]) {
willBeKilled[targetR][targetC] = true;
killsThisTurn++;
}
}
} // 모든 궁수 표적 탐색 끝
// 표적 제거
totalKilled += killsThisTurn;
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
if (willBeKilled[r][c])
map[r][c] = 0;
}
}
// 적 이동: 아래로 한 칸 (N-1 행의 적은 성으로 들어가 제거)
// 아래에서 위로 이동시키면 덮어쓰기 없이 처리 가능
for (int r = N - 1; r >= 1; r--) {
for (int c = 0; c < M; c++) {
map[r][c] = map[r - 1][c];
}
}
// 최상단 행은 빈칸이 됨
for (int c = 0; c < M; c++)
map[0][c] = 0;
// 만약 남은 적이 없다면 더 이상 진행할 필요 없음
boolean any = false;
for (int r = 0; r < N && !any; r++) {
for (int c = 0; c < M; c++) {
if (map[r][c] == 1) {
any = true;
break;
}
}
}
if (!any)
break;
}
return totalKilled;
}
}
마무리
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.
Junior backend developer