📚 Problem
📝 Solution
- 거리가 D 이하인 적중에서 가장 가까운 적을 공격
- 만약 위의 경우가 여럿일 경우, 가장 왼쪽의 적을 공격
- 여러명의 궁수에게 공격 당하는 것이 가능
- 궁수의 자리가 1 ~ M 중에서 3개를 뽑는 조합 문제
- 궁수의 공격으로 제외되는 적 의 최대수 구하기
- 궁수의 위치를 저장한 객체배열을 이용해 반복문을 돌립니다
- 거리가 가장 가까운 적을 찾아야 하기때문에, 적이 있으면 거리를 비교하여 더 적은 거리라면 최소 거리의 적의 위치를 갱신합니다
- 만약 같은거리라면 열의 값을 비교하여 더 왼쪽의 위치를 선택하여 갱신합니다
- 가장 가까운 적의 위치를 찾은 후 거리가 D 이하라면 indexToKill 의 배열의 위치를 true로 바꿔줍니다
- 적을 공격하고 바로 0 으로 안바꾸는 것은 한명의 적을 여러 궁수가 공격할 수 있기 때문에
- 먼저 indexToKill 배열에서 위치만 지정하고 이후에 배열의 값을 0으로 바꿔주고 궁수에게 공격당한 적의 수를 카운트합니다
for(Node archer : archers){
Node enemy = new Node(Integer.MAX_VALUE, Integer.MAX_VALUE);
int enemyD = Integer.MAX_VALUE;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
if(copiedGame[i][j] == 1){
if(enemyD > enemyDistance(archer, i, j)){
enemy.r = i;
enemy.c = j;
enemyD = enemyDistance(archer, i, j);
}
if(enemyD == enemyDistance(archer, i, j))
if(enemy.c > j){
enemy.r = i;
enemy.c = j;
}
}
if(enemyD <= D)
indexToKill[enemy.r][enemy.c] = true;
}- 조합을 이용하여 M개의 자리중에서 3자리를 뽑는 것을 DFS 로 구현
- 인덱스 3개를 뽑은 후 game 배열을 복사하여 N + 1 행에
- 해당 인덱스 3개에 궁수를 -1의 값으로 넣어준다
private static void DFS(int depth){
if(depth == 3){
int[][] tmpGame = copyGame();
for(int index : order)
tmpGame[N + 1][index] = -1;
play(tmpGame);
return;
}
for(int i = 1; i <= M; i++)
if(!visited[i]){
visited[i] = true;
order[depth] = i;
DFS(depth + 1);
visited[i] = false;
}
}💻 Code
import java.util.Scanner;
class Node{
int r;
int c;
public Node(int r, int c){
this.r = r;
this.c = c;
}
}
public class Main {
private static int N, M, D, max;
private static int[] archer;
private static int[] order;
private static boolean[] visited;
private static int[][] game;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
M = scanner.nextInt();
D = scanner.nextInt();
order = new int[3];
visited = new boolean[M + 1];
archer = new int[M + 1];
for(int i = 1; i <= M; i++)
archer[i] = i;
game = new int[N + 2][M + 1];
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
game[i][j] = scanner.nextInt();
DFS(0);
System.out.println(max);
scanner.close();
}
private static int[][] copyGame(){
int[][] tmpGame = new int[N + 2][M + 1];
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
tmpGame[i][j] = game[i][j];
return tmpGame;
}
private static boolean isAllDead(int[][] copiedGame){
boolean check = true;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
if(copiedGame[i][j] == 1){
check = false;
break;
}
return check;
}
private static void moveEnemies(int[][] copiedGame){
for(int i = N; i >= 1; i--)
for(int j = 1; j <= M; j++)
if(copiedGame[i][j] == 1){
if(i == N)
copiedGame[i][j] = 0;
else{
copiedGame[i][j] = 0;
copiedGame[i + 1][j] = 1;
}
}
}
private static int enemyDistance(Node archer, int x, int y){
return Math.abs(archer.r - x) + Math.abs(archer.c - y);
}
private static void play(int[][] copiedGame){
int killByArcher = 0;
Node[] archers = new Node[3];
int index = 0;
for(int j = 1; j <= M; j++)
if(copiedGame[N + 1][j] == -1)
archers[index++] = new Node(N + 1, j);
while (!isAllDead(copiedGame)) {
boolean[][] indexToKill = new boolean[N + 1][M + 1];
for(Node archer : archers){
Node enemy = new Node(Integer.MAX_VALUE, Integer.MAX_VALUE);
int enemyD = Integer.MAX_VALUE;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
if(copiedGame[i][j] == 1){
if(enemyD > enemyDistance(archer, i, j)){
enemy.r = i;
enemy.c = j;
enemyD = enemyDistance(archer, i, j);
}
if(enemyD == enemyDistance(archer, i, j))
if(enemy.c > j){
enemy.r = i;
enemy.c = j;
}
}
if(enemyD <= D)
indexToKill[enemy.r][enemy.c] = true;
}
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
if(indexToKill[i][j]){
copiedGame[i][j] = 0;
killByArcher++;
}
moveEnemies(copiedGame);
}
max = Math.max(max, killByArcher);
}
private static void DFS(int depth){
if(depth == 3){
int[][] tmpGame = copyGame();
for(int index : order)
tmpGame[N + 1][index] = -1;
play(tmpGame);
return;
}
for(int i = 1; i <= M; i++)
if(!visited[i]){
visited[i] = true;
order[depth] = i;
DFS(depth + 1);
visited[i] = false;
}
}
}
New, Strange, Want to try