문제
https://www.acmicpc.net/problem/17135
풀이
N×M격자판N+1행에는 성- 성에는 궁수 3명 배치
- 거리가
D이하인 적 중 가까운 적을 타겟으로 정함 - 같은 거리의 적이 여럿일 경우 가장 왼쪽을 선택
- 궁수들이 한 번에 같은 적을 공격할 수 있음
- 공격 후, 적은 아래로 한 칸씩 이동
- 모든 적이 격자판에서 제외되면, 게임 끝
- 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력
- 궁수와 적의 거리는 맨해튼 거리로 계산
상당히 복잡한 구현, 시뮬레이션 문제입니다.
구현해야 할 것들을 리스트화 해보겠습니다.
- 입력 및 맵 초기화
m개의 성 중 3곳에 궁수를 배치하는 메서드(조합)- 배치된 궁수들 기준 사거리 이내이면서 가장 가까운 적 탐색
- 적 이동 구현
크게 나누자면 이렇게 나눠볼 수 있겠네요.
바로 시작하겠습니다.
입력
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()); // 궁수 사거리
// 지도 초기화
map = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 궁수가 위치한 인덱스를 저장할 배열
pos = new int[3];- 3명의 궁수를 0부터
M-1까지 배치해야 하므로 nC3의 조합을 구해야 합니다. - 해당 위치를 저장할 배열
pos를 미리 선언했습니다.
궁수 배치(조합)
private static void permutation(int depth, int start) {
// 최대 깊이 도달했다면 시뮬레이션 시작
if (depth == 3) {
answer = Math.max(answer, simulate()); // 최댓값 갱신
return;
}
// 조합
for (int i = start; i < m; i++) {
pos[depth] = i;
permutation(depth + 1, i + 1); // 재귀
}
}M개의 위치에 3명의 궁수를 배치
시뮬레이션
private static int simulate() {
// 적을 제거하고 이동 시키는 행위를
// 모든 조합을 이용해서 시뮬레이션해야 하므로
// 원본 배열을 해치지 않게, 깊은 복사하여 사용했습니다.
int[][] temp = new int[n][m];
for (int i = 0; i < n; i++) temp[i] = map[i].clone();
int killed = 0; // 제거한 적의 수
while (true) {
// 격자판 내에 적이 있는지 탐색
boolean flag = false;
Search:
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp[i][j] == 1) {
flag = true;
break Search;
}
}
}
if (!flag) break; // 적이 없다면 시뮬레이션 종료
// 각 궁수별로 가장 가까운 적 탐색
Pos target1 = findTarget(pos[0], temp);
Pos target2 = findTarget(pos[1], temp);
Pos target3 = findTarget(pos[2], temp);적 탐색
private static Pos findTarget(int p, int[][] temp) {
// 모든 적들의 좌표와 거리 정보를 저장
List<Pos> candidates = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp[i][j] == 1) {
int dist = Math.abs(n - i) + Math.abs(p - j); // 거리 계산
candidates.add(new Pos(i, j, dist));
}
}
}
if (candidates.isEmpty()) return null; // 적이 없다면 리턴(안전 장치)
Collections.sort(candidates); // 적들을 정렬
if (candidates.get(0).dist > d) return null; // 만약 가장 가까운 적의 거리가 사정거리 밖이라면 리턴
return candidates.get(0); // 사정 거리 내에 있으면서, 가장 왼쪽에 있는 적 리턴
}적의 좌표를 관리할 클래스
static class Pos implements Comparable<Pos> {
int r, c, dist; // 좌표, 거리
public Pos (int r, int c, int dist) {
this.r = r;
this.c = c;
this.dist = dist;
}
@Override
public int compareTo(Pos o) {
if (this.dist != o.dist) { // 거리가 다르다면, 거리순으로 정렬
return Integer.compare(this.dist, o.dist);
}
return Integer.compare(this.c, o.c); // 거리가 같다면 열 기준 정렬
}
}- 적들의 정보를 관리하기 편하게 클래스를 선언하였습니다.
compareTo를 재정의하면, 정렬했을 때 원하는 대로 결과가 나오게 할 수 있습니다.
다시 시뮬레이션 코드입니다.
// 위에서 찾아낸 적들의 정보를 저장(null이 아닐 경우에만)
List<Pos> targets = new ArrayList<>();
if (target1 != null) targets.add(target1);
if (target2 != null) targets.add(target2);
if (target3 != null) targets.add(target3);
// 적 사살 시작
for (Pos t : targets) {
if (temp[t.r][t.c] == 1) { // 적이 있을 경우에
temp[t.r][t.c] = 0; // 적 제거
++killed; // 제거 횟수 증가
}
}
temp = moved(temp); // 적들 아래로 이동
}
return killed;
}- 적이 있을 경우라는 조건문을 추가한 이유는, 같은 적을 여러 궁수들이 노리고 있을 수 있기 때문입니다.
- 이미 제거가 되었다면,
killed를 카운팅하지 않기 위해 선언했습니다.
적 이동
private static int[][] moved(int[][] temp) {
for (int i = n-1; i > 0; i--) {
for (int j = 0; j < m; j++) {
temp[i][j] = temp[i-1][j]; // 아래로 한 칸씩 내리기
}
}
Arrays.fill(temp[0], 0); // 첫 번째 행은 0으로 채우기
return temp;
}- 아래에서부터 위 행을 내려줬습니다.
- 첫 번째 행은 0으로 모두 덮어씌웠습니다.
이런 식으로 계속 반복하면서 모든 조합을 구해냈습니다.
마지막으로 리턴한 killed를 통해 최댓값을 계속 갱신하면서 진행하다, 시뮬레이션이 끝나면 이를 출력해주면 끝입니다.
출력
permutation(0, 0);
System.out.println(answer);코드
import java.util.*;
import java.io.*;
public class Main_17135 {
static class Pos implements Comparable<Pos> {
int r, c, dist;
public Pos (int r, int c, int dist) {
this.r = r;
this.c = c;
this.dist = dist;
}
@Override
public int compareTo(Pos o) {
if (this.dist != o.dist) {
return Integer.compare(this.dist, o.dist);
}
return Integer.compare(this.c, o.c);
}
}
static int n, m, d;
static int[] pos;
static int[][] map;
static int answer = 0;
private static void permutation(int depth, int start) {
if (depth == 3) {
answer = Math.max(answer, simulate());
return;
}
for (int i = start; i < m; i++) {
pos[depth] = i;
permutation(depth + 1, i + 1);
}
}
private static int simulate() {
int[][] temp = new int[n][m];
for (int i = 0; i < n; i++) temp[i] = map[i].clone();
int killed = 0;
while (true) {
boolean flag = false;
Search:
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp[i][j] == 1) {
flag = true;
break Search;
}
}
}
if (!flag) break;
Pos target1 = findTarget(pos[0], temp);
Pos target2 = findTarget(pos[1], temp);
Pos target3 = findTarget(pos[2], temp);
List<Pos> targets = new ArrayList<>();
if (target1 != null) targets.add(target1);
if (target2 != null) targets.add(target2);
if (target3 != null) targets.add(target3);
for (Pos t : targets) {
if (temp[t.r][t.c] == 1) {
temp[t.r][t.c] = 0;
++killed;
}
}
temp = moved(temp);
}
return killed;
}
private static Pos findTarget(int p, int[][] temp) {
List<Pos> candidates = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp[i][j] == 1) {
int dist = Math.abs(n - i) + Math.abs(p - j);
candidates.add(new Pos(i, j, dist));
}
}
}
if (candidates.isEmpty()) return null;
Collections.sort(candidates);
if (candidates.get(0).dist > d) return null;
return candidates.get(0);
}
private static int[][] moved(int[][] temp) {
for (int i = n-1; i > 0; i--) {
for (int j = 0; j < m; j++) {
temp[i][j] = temp[i-1][j];
}
}
Arrays.fill(temp[0], 0);
return temp;
}
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());
map = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
pos = new int[3];
permutation(0, 0);
System.out.println(answer);
}
}