문제 소개
해당 문제는 격자판에서 적이 있을 때 최하단에 궁수를 배치하고 공격 -> 적 한칸 아래 이동하는 순서로 진행할 경우 처치 가능한 수를 물어보는 문제이다.
문제를 해결하기 위해 아래의 기능 요구사항을 정리하였다.
- 3명의 궁수 배치
- 배치된 각 궁수들의 타겟 위치
- 적 이동
1번은 판의 최대 크기가 15이고 3명의 궁수로 지정했기 때문에 DFS로 해도 문제가 없을 것이다.
public static void setArchers(List<int[]> archerPos, int cnt, int archer, int[] pos) {
if (cnt == 3) {
archerPos.add(Arrays.copyOf(pos, 3));
return;
}
for (int i = archer + 1; i < M; i++) {
pos[cnt] = i;
setArchers(archerPos, cnt + 1, i, pos);
pos[cnt] = -1;
}
}2번은 배치된 궁수들의 위치에서 제일 가까운 적들을 바로 처치하면 안된다. 궁수들끼리 중복된 적을 타겟으로 삼을 수 있기 때문에 궁수들의 타겟들을 통합하여 처치하여야 한다.
public static int[] getAttack(int bottom, int archer, boolean[][] enemy) {
if (enemy[bottom - 1][archer]) {
return new int[]{bottom - 1, archer};
}
int[] canAttackEnemy = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
int canAttackEnemyDistance = Integer.MAX_VALUE;
Queue<int[]> needVisited = new LinkedList<>();
needVisited.add(new int[]{bottom - 1, archer, 1});
boolean[][] visited = new boolean[N][M];
visited[bottom - 1][archer] = true;
while (!needVisited.isEmpty()) {
int[] now = needVisited.poll();
if (now[2] > D || now[2] > canAttackEnemyDistance) {
continue;
}
if (enemy[now[0]][now[1]]) {
if (now[2] < canAttackEnemyDistance) {
canAttackEnemyDistance = now[2];
canAttackEnemy[0] = now[0];
canAttackEnemy[1] = now[1];
} else if (now[2] == canAttackEnemyDistance && now[1] < canAttackEnemy[1]) {
canAttackEnemy[0] = now[0];
canAttackEnemy[1] = now[1];
}
}
for (int i = 0; i < 4; i++) {
int nextY = now[0] + CONTROL_Y[i];
int nextX = now[1] + CONTROL_X[i];
if (-1 < nextY && nextY < N && -1 < nextX && nextX < M && !visited[nextY][nextX] && nextY < bottom) {
needVisited.add(new int[]{nextY, nextX, now[2] + 1});
visited[nextY][nextX] = true;
}
}
}
return canAttackEnemy;
}3번이 사실 가장 많이 고민하였다. 적들을 O(N * N)으로 서치해서 하기엔 시간이 많이 걸릴것 같아 애초에 궁수들이 있는 성을 움직이는 형태(하울의 움직이는 성과 같이)로 작성해볼것이다.
3번 문제 발생
import java.io.*;
import java.util.*;
public class Main {
private static final int[] CONTROL_Y = {0, 0, 1, -1};
private static final int[] CONTROL_X = {1, -1, 0, 0};
private static int N, M, D;
private static int ans = 0;
private static int lastEnemy = N - 1;
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());
List<int[]> archerPos = new ArrayList<>();
boolean[][] enemy = new boolean[N][M];
for (int i = 0; i < N; i++) {
String[] enemyLine = br.readLine().split(" ");
for (int j = 0; j < M; j++) {
if (enemyLine[j].equals("1")) {
enemy[i][j] = true;
lastEnemy = Math.min(lastEnemy, i);
}
}
}
setArchers(archerPos, 0, -1, new int[]{-1, -1, -1});
for (int[] archers : archerPos) {
int removeCnt = 0;
boolean[][] enemyPos = copy2d(enemy);
for (int bottom = N; bottom > lastEnemy; bottom--) {
if (bottom == 0) {
break;
}
List<int[]> attackTarget = new ArrayList<>();
for (int archer : archers) {
int[] target = getAttack(bottom, archer, enemyPos);
if (target[0] != Integer.MAX_VALUE) {
attackTarget.add(target);
}
}
for (int[] removeEnemy : attackTarget) {
if (enemyPos[removeEnemy[0]][removeEnemy[1]]) {
enemyPos[removeEnemy[0]][removeEnemy[1]] = false;
removeCnt++;
}
}
}
ans = Math.max(ans, removeCnt);
}
System.out.println(ans);
}
public static void setArchers(List<int[]> archerPos, int cnt, int archer, int[] pos) {
if (cnt == 3) {
archerPos.add(Arrays.copyOf(pos, 3));
return;
}
for (int i = archer + 1; i < M; i++) {
pos[cnt] = i;
setArchers(archerPos, cnt + 1, i, pos);
pos[cnt] = -1;
}
}
public static boolean[][] copy2d(boolean[][] arr) {
boolean[][] result = new boolean[N][];
for (int i = 0; i < N; i++) {
result[i] = Arrays.copyOf(arr[i], M);
}
return result;
}
public static int[] getAttack(int bottom, int archer, boolean[][] enemy) {
if (enemy[bottom - 1][archer]) {
return new int[]{bottom - 1, archer};
}
int[] canAttackEnemy = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
int canAttackEnemyDistance = Integer.MAX_VALUE;
Queue<int[]> needVisited = new LinkedList<>();
needVisited.add(new int[]{bottom - 1, archer, 1});
boolean[][] visited = new boolean[N][M];
visited[bottom - 1][archer] = true;
while (!needVisited.isEmpty()) {
int[] now = needVisited.poll();
if (now[2] > D || now[2] > canAttackEnemyDistance) {
continue;
}
if (enemy[now[0]][now[1]]) {
if (now[2] < canAttackEnemyDistance) {
canAttackEnemyDistance = now[2];
canAttackEnemy[0] = now[0];
canAttackEnemy[1] = now[1];
} else if (now[2] == canAttackEnemyDistance && now[1] < canAttackEnemy[1]) {
canAttackEnemy[0] = now[0];
canAttackEnemy[1] = now[1];
}
}
for (int i = 0; i < 4; i++) {
int nextY = now[0] + CONTROL_Y[i];
int nextX = now[1] + CONTROL_X[i];
if (-1 < nextY && nextY < N && -1 < nextX && nextX < M && !visited[nextY][nextX]) {
needVisited.add(new int[]{nextY, nextX, now[2] + 1});
visited[nextY][nextX] = true;
}
}
}
return canAttackEnemy;
}
}위의 코드에서 BFS를 이용해서 궁수의 사거리 안의 적들 중 가장 가까운 적들을 서칭하였다.
하지만 해당 코드 제출했을 때 문제점이 발생하였다.
문제는 3번 기능에서 성을 움직일때 발생한다.
성이 움직일 경우, 처치 못한 적들이 성이 있는 라인에 도착할 경우 제외해야 한다. 하지만, 해당 코드는 성이 적들을 있는 라인에 도착했을 경우 제외하지 못하고 성이 고정된것 처럼 너비 탐색을 진행하고 있다.
그럼으로 해당 코드에서 bottom보다 작을 경우에만 탐색하도록 했더니 코드가 정상 탐색되었다.
문제 해결 코드
정리하자면 적들을 탐색하고 중복에 유의하여 적들을 처치한 다음, 움직이는 성과 같이 성을 움직여서 해당 부분을 O(N^2)에서 O(N)으로 시간 복잡도를 줄였다.
당연히 성이 움직이니까, 탐색할 수 있는 범위도 성의 위쪽만 탐색해야할 것이다.
import java.io.*;
import java.util.*;
public class Main {
private static final int[] CONTROL_Y = {0, 0, 1, -1};
private static final int[] CONTROL_X = {1, -1, 0, 0};
private static int N, M, D;
private static int ans = 0;
private static int lastEnemy = N - 1;
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());
List<int[]> archerPos = new ArrayList<>();
boolean[][] enemy = new boolean[N][M];
for (int i = 0; i < N; i++) {
String[] enemyLine = br.readLine().split(" ");
for (int j = 0; j < M; j++) {
if (enemyLine[j].equals("1")) {
enemy[i][j] = true;
lastEnemy = Math.min(lastEnemy, i);
}
}
}
setArchers(archerPos, 0, -1, new int[]{-1, -1, -1});
for (int[] archers : archerPos) {
int removeCnt = 0;
boolean[][] enemyPos = copy2d(enemy);
for (int bottom = N; bottom > lastEnemy; bottom--) {
if (bottom == 0) {
break;
}
List<int[]> attackTarget = new ArrayList<>();
for (int archer : archers) {
int[] target = getAttack(bottom, archer, enemyPos);
if (target[0] != Integer.MAX_VALUE) {
attackTarget.add(target);
}
}
for (int[] removeEnemy : attackTarget) {
if (enemyPos[removeEnemy[0]][removeEnemy[1]]) {
enemyPos[removeEnemy[0]][removeEnemy[1]] = false;
removeCnt++;
}
}
}
ans = Math.max(ans, removeCnt);
}
System.out.println(ans);
}
public static void setArchers(List<int[]> archerPos, int cnt, int archer, int[] pos) {
if (cnt == 3) {
archerPos.add(Arrays.copyOf(pos, 3));
return;
}
for (int i = archer + 1; i < M; i++) {
pos[cnt] = i;
setArchers(archerPos, cnt + 1, i, pos);
pos[cnt] = -1;
}
}
public static boolean[][] copy2d(boolean[][] arr) {
boolean[][] result = new boolean[N][];
for (int i = 0; i < N; i++) {
result[i] = Arrays.copyOf(arr[i], M);
}
return result;
}
public static int[] getAttack(int bottom, int archer, boolean[][] enemy) {
if (enemy[bottom - 1][archer]) {
return new int[]{bottom - 1, archer};
}
int[] canAttackEnemy = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
int canAttackEnemyDistance = Integer.MAX_VALUE;
Queue<int[]> needVisited = new LinkedList<>();
needVisited.add(new int[]{bottom - 1, archer, 1});
boolean[][] visited = new boolean[N][M];
visited[bottom - 1][archer] = true;
while (!needVisited.isEmpty()) {
int[] now = needVisited.poll();
if (now[2] > D || now[2] > canAttackEnemyDistance) {
continue;
}
if (enemy[now[0]][now[1]]) {
if (now[2] < canAttackEnemyDistance) {
canAttackEnemyDistance = now[2];
canAttackEnemy[0] = now[0];
canAttackEnemy[1] = now[1];
} else if (now[2] == canAttackEnemyDistance && now[1] < canAttackEnemy[1]) {
canAttackEnemy[0] = now[0];
canAttackEnemy[1] = now[1];
}
}
for (int i = 0; i < 4; i++) {
int nextY = now[0] + CONTROL_Y[i];
int nextX = now[1] + CONTROL_X[i];
if (-1 < nextY && nextY < N && -1 < nextX && nextX < M && !visited[nextY][nextX]) {
needVisited.add(new int[]{nextY, nextX, now[2] + 1});
visited[nextY][nextX] = true;
}
}
}
return canAttackEnemy;
}
}
내게 남은 소중한 자식은 누군지 아나? 쑨양이다!