✨ 문제
🎈 접근 방식
- 3명의 궁수를 5개의 열에 배치하기 위해 조합을 사용해서 모든 경우를 뽑아낸다.
- 궁수가 배치된 조합별로 몬스터를 잡아주는데 사정거리 안에 들어있는지 확인해준다.
- 적을 잡게 되면 카운트 +1씩 해주면서 최종적으로 최댓값을 답으로 출력시킨다.
일단 궁수 3명을 배치하는 것은 조합을 사용하기로 했고, 궁수가 배치될 때 마다 적들의 위치 원본을 사용하는게 아닌 복사본을 사용해줘야 한다.
그리고, 하나의 적은 여러 궁수에게 공격당할 수 있다는 것이 핵심이다!! 그렇기 때문에 바로 적이 해당한 좌표를 지우지 않고 체크만 해두고 나중에 한번에 지우도록 처리를 해야 함
😫 실수한 점이나 놓친 점
여러 실수들이 좀 있었다.. 특히 적을 잡는 함수를 구현하는 과정에서였다.
적의 위치 정보를 복사해서 사용하려고 했고 나는 죽은 적을 표시하려고 class에 isDead로 표시를 했다. 근데 답이 이상하게 나오길래 출력을 찍어본 결과, 위치 정보만 바꾸었지 이전의 적이 죽었는지 여부가 그대로 남아있었다.
예를 들어서 궁수 3명이 사정거리가 1이고 {5,0}, {5,1}, {5,2}에 배치되어 있는 경우 적은 {4,0}, {4,1}, {4,2} 3명의 적을 잡을 수 있다.
이때, 3명의 적은 isDead가 true로 되어 있고 dead는 3이 되는거지만, 내 이전 코드상 그 다음 궁수가 배치되는 경우에도 [{4,0}, {4,1}, {4,2}] 이 3명의 적의 isDead는 true로 되어 있던 것이다.
경우마다 새롭게 써주려고 했지만 결국 안되서 보니 .clear()를 통해서 비워준 뒤 그때마다 추가해주도록 했다.
💻 틀렸던 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int n, m, d, ans;
static int[] arrow;
static List<Monster> enemy = new ArrayList<>(); // 적의 위치를 담을 공간
static PriorityQueue<Monster> pq = new PriorityQueue<>((e1, e2) -> e1.h == e2.h ? e1.y - e2.y : e1.h - e2.h);
public static void main(String[] args) throws Exception {
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());
arrow = new int[3];
// map에 기록하는 동시에 적의 위치를 저장해주고
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
int xy = Integer.parseInt(st.nextToken());
if (xy == 1) {
enemy.add(new Monster(i, j));
}
}
}
locate(0, 0);
System.out.println(ans);
}
// 궁수 3명을 배치
static void locate(int srcIdx, int tgtIdx) {
if (tgtIdx == 3) {
// 공격전에 기존 몬스터 배치를 복사해서 카운트를 하도록
List<Monster> copy = copy(enemy);
attack(copy);
return;
}
for (int i = srcIdx; i < m; i++) {
arrow[tgtIdx] = i;
locate(i + 1, tgtIdx + 1);
}
}
// 적을 제거
static void attack(List<Monster> list) {
int dead = 0;
while (true) {
for (int i = 0; i < 3; i++) { // 각 궁수마다 잡을 몬스터
pq.clear();
for (int j = 0; j < list.size(); j++) { // 몬스터와의 거리를 계산해서 사정거리 안에 있는지
Monster monster = list.get(j);
monster.h = Math.abs(monster.x - n) + Math.abs(monster.y - arrow[i]);
if (monster.h <= d) {
// System.out.println("d= " + d + "dis= "+ dis);
pq.offer(monster);
}
}
// for (Monster monster : pq) {
// System.out.println("monster.x" + monster.x + " monster.y = " + monster.y);
// }
// pq안에 있는 몬스터들은 죽었다라고 표시를 해두고
if (!pq.isEmpty()) {
pq.poll().isDead = true;
}
}
// System.out.println("====");
// 죽은 적군을 enemy 제거, 남은 적군 한 칸 아래로 이동, 경계선을 벗어나면 enemy 에서 제거
for (int i = list.size() - 1; i >= 0; i--) {
Monster e = list.get(i);
if (e.isDead) {
// System.out.println("e.x" + e.x + " e.y = " + e.y);
list.remove(i);
dead++;
} else if (e.x == n - 1) {
list.remove(i);
} else {
e.x++;
}
}
// System.out.println("=====");
if (list.size() == 0) {
break;
}
}
ans = Math.max(ans, dead);
}
static List<Monster> copy(List<Monster> list) {
List<Monster> temp = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
Monster monster = list.get(i);
temp.add(new Monster(monster.x, monster.y));
}
return temp;
}
static class Monster {
int x;
int y;
int h;
boolean isDead;
public Monster(int x, int y) {
this.x = x;
this.y = y;
}
}
}기존 코드에서 new를 통해 Monster객체를 새로 생성해서 넣어줘야 전부 초기화가 된다!! 이걸 안해줘서 틀렸었다..
💻 정답 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int n, m, d, ans;
static int[] arrow;
static List<Monster> enemyCopy = new ArrayList<>();
static List<Monster> enemy = new ArrayList<>(); // 적의 위치를 담을 공간
static PriorityQueue<Monster> pq = new PriorityQueue<>((e1, e2) -> e1.h == e2.h ? e1.y - e2.y : e1.h - e2.h);
public static void main(String[] args) throws Exception {
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());
arrow = new int[3];
// map에 기록하는 동시에 적의 위치를 저장해주고
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
int xy = Integer.parseInt(st.nextToken());
if (xy == 1) {
enemy.add(new Monster(i, j));
}
}
}
locate(0, 0);
System.out.println(ans);
}
// 궁수 3명을 배치
static void locate(int srcIdx, int tgtIdx) {
if (tgtIdx == 3) {
// 공격전에 기존 몬스터 배치를 복사해서 카운트를 하도록
attack();
return;
}
for (int i = srcIdx; i < m; i++) {
arrow[tgtIdx] = i;
locate(i + 1, tgtIdx + 1);
}
}
// 적을 제거
static void attack() {
int dead = 0;
enemyCopy.clear();
for (Monster e : enemy) {
enemyCopy.add(new Monster(e.x, e.y)); // 객체를 공유하지 않고, 내용만 복사해서 새로운 객체 생성
}
while (true) {
for (int i = 0; i < 3; i++) { // 각 궁수마다 잡을 몬스터
pq.clear();
for (int j = 0; j < enemyCopy.size(); j++) { // 몬스터와의 거리를 계산해서 사정거리 안에 있는지
Monster monster = enemyCopy.get(j);
monster.h = Math.abs(monster.x - n) + Math.abs(monster.y - arrow[i]);
if (monster.h <= d) {
// System.out.println("d= " + d + "dis= "+ dis);
pq.offer(monster);
}
}
// pq안에 있는 몬스터들은 죽었다라고 표시를 해두고
if (!pq.isEmpty()) {
pq.poll().isDead = true;
}
}
// 죽은 적군을 enemy 제거, 남은 적군 한 칸 아래로 이동, 경계선을 벗어나면 enemy 에서 제거
for (int i = enemyCopy.size() - 1; i >= 0; i--) {
Monster e = enemyCopy.get(i);
if (e.isDead) {
enemyCopy.remove(i);
dead++;
} else if (e.x == n - 1) {
enemyCopy.remove(i);
} else {
e.x++;
}
}
if (enemyCopy.size() == 0) {
break;
}
}
ans = Math.max(ans, dead);
}
static List<Monster> copy(List<Monster> list) {
List<Monster> temp = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
Monster monster = list.get(i);
temp.add(monster);
}
return temp;
}
static class Monster {
int x;
int y;
int h;
boolean isDead;
public Monster(int x, int y) {
this.x = x;
this.y = y;
}
}
}
능동적으로 개발 지식을 찾아다니는 백엔드 개발자입니다 😊 작성된 글에 대한 질문들 및 피드백은 언제나 환영입니다 :) 👌