🔰 문제
💡 접근방식
- 궁수의 자리(열)을 배치 -> M개의 열에서 3개 열 뽑는 조합
- 궁수 배치 후, 각 궁수들마다 공격할 수 있는 적들 리스트 생성 후, 그 중 가장 가깝고, 왼쪽에 있는 적 공격
- 공격이 끝나면 적들 아래로 이동
- 2~3을 적들이 map에서 다 사라질 때까지 반복
생각한 로직은 위와 같다.
이를 구현하기 위해 궁수의 열 자리를 저장하는 int archer[3] 배열을 생성하였다.
locateArcher(int idx, int start) - 궁수 자리 배치
attackMonster(List<int[]> list) - 궁수가 적 공격 후, 적들 아래로 이동(이를 적 리스트가 빌 때까지 반복)
또한 적의 정보를 관리하기 위해서 직접 map[N][M] 배열에서 2차원 탐색할 수도 있었는데, 나는 적 정보를 따리 관리하는 ArrayList를 생성하였다.
이 문제에서 유의해야 할 키포인트는
-
궁수의 사격 거리 중 가장 가까운 적, 가까운 적이 많다면 가장 왼쪽에 있는 적을 우선으로 제거하는 것
-
궁수는 같은 적을 공격할 수 있음
이었는데 이를 구현하기 위해
- 궁수의 사격 거리 중 가장 가까운 적, 가까운 적이 많다면 가장 왼쪽에 있는 적
-> 적의 x좌표, y좌표, 궁수와의 거리를 저장하는 커스텀 클래스를 생성하여 Comparable 인터페이스를 이용하여 거리순, 왼쪽위치(열 작은) 순으로 정렬시켜도록 만들고 궁수의 사격 거리 안에 있는 적들을 PriorityQueue에 넣었다. 그러면 Prioirty Queue 안에서 알아서 정렬해주기 때문에 큐 안의 첫번째 값을 뽑으면 조건을 만족하는 적인 것이다.
static class Monster implements Comparable<Monster>{
int x, y, d; //행, 열, 거리
public Monster(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
@Override
public int compareTo(Monster o) {
if(this.d==o.d) { //거리가 같다면
return this.y-o.y; //열이 더 작은 값(더 왼쪽)
}else
return this.d-o.d; //거리가 더 작은 값
}
}- 궁수는 같은 적을 공격할 수 있음
위에서 적을 우선순위 큐에 넣어 관리한다 하였는데, 만약 위 조건으로 따졌을 때 A라는 몬스터를 궁수 2명이 만족한다고 친다고 하자.
만약 첫번째 궁수가 가장 가까운 애인 A를 찾아서 바로 제거해버리면, 다음 궁수가 A라는 몬스터를 원래는 제거했어야 했는데 사라져서 다른 적을 제거하게 된다.
그러므로 PQ에서 꺼내가지고, targets 라는 리스트에 별도로 적의 정보를 관리하게 하여 각 궁수들마다 제거할 적 리스트를 저장하였다.
💦 풀면서 실수, 놓친 점
-
궁수의 자리를 배치하고 나서, 적 리스트를 관리할 때 아무 생각없이 static 변수로 사용한 궁수를 그대로 사용하였다.
그랬더니 궁수 3명 자리 배치 첫번째 조합에서만 정상적으로 작동하고,
두번째 조합에서부턴 이미 이전에 난도질당한(?) 적 리스트로 다시 로직을 실행했기 때문에 정상적인 값이 안 나온다.
항상 브루트 포스로 조합을 만들어, 로직을 실행할 땐 값을 현재의 상태값을 백업해두자. -
리스트 복사 때 고생함
맞은 케이스
int[] 리스트를 복사할 땐 int[] 값들을 원본 리스트에서 꺼내와서 복사해줘야 한다..
private static List<int[]> copy(List<int[]> list) {
List<int[]> tmp = new ArrayList<>();
for(int i=0;i<list.size();i++) {
int[] cur = list.get(i);
tmp.add(new int[] {cur[0], cur[1]});
}
return tmp;
} 틀린 케이스
이와 같이 list.get(i)로 int[] 뭉텅이를 복사해오면 처음엔 값 출력했을 때 맞아 보이는 것 같아도 카피한 배열에서 값을 변경하면 원본도 함께 영향 받아버려서 복사한 의미가 없어진다..
int[]는 레퍼런스 타입이기 때문이다!!!
private static List<int[]> copy(List<int[]> list) {
List<int[]> tmp = new ArrayList<>();
for(int i=0;i<list.size();i++) {
tmp.add(list.get(i));
}
return tmp;
}🕑 소요시간
65분
💻 풀이
package com.boj;
import java.io.*;
import java.util.*;
public class Main_17135 {
static class Monster implements Comparable<Monster> {
int x, y, d; // 행, 열, 거리
public Monster(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
@Override
public int compareTo(Monster o) {
if (this.d == o.d) { // 거리가 같다면
return this.y - o.y; // 열이 더 작은 값(더 왼쪽)
} else
return this.d - o.d; // 거리가 더 작은 값
}
}
static int N, M, D;
static int map[][];
static List<int[]> list;
static int archer[];
static int res; // 공격할 수 있는 최대 적 수(정답)
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()); // 궁수의 공격 거리
map = new int[N][M];
archer = new int[3]; // 궁수 3명의 공격 위치(열) 저장
list = new ArrayList<>(); // 몬스터 좌표 저장
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());
if (map[i][j] == 1) // 몬스터 좌표
list.add(new int[] { i, j });
}
}
locateArcher(0, 0); // 궁수 3명 배치(조합)
System.out.println(res);
}
private static void locateArcher(int idx, int start) {
if (idx == 3) { // 3명 다 배치했으면
List<int[]> data = copy(list);
attackMonster(data); // 몬스터 공격하러 가기
return;
}
for (int i = start; i < M; i++) {
archer[idx] = i;
locateArcher(idx + 1, i + 1);
}
}
private static List<int[]> copy(List<int[]> list) { // 몬스터 좌표 리스트 복사
List<int[]> tmp = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
int[] cur = list.get(i);
tmp.add(new int[] { cur[0], cur[1] });
}
return tmp;
}
private static void attackMonster(List<int[]> list) {
int count = 0; // 공격한 몬스터 수
while (true) {
if (list.isEmpty()) // 더이상 적 없으면
break;
List<int[]> targets = new ArrayList<>(); // 궁수 3명이 공격하고자 하는 적의 좌표
for (int k = 0; k < 3; k++) { // 각 궁수마다 잡을 몬스터 설정
PriorityQueue<Monster> pq = new PriorityQueue<>(); // 현재 궁수의 사정거리에 있는 몬스터들 저장(거리 순, 열 순 정렬)
for (int i = 0; i < list.size(); i++) { // 현재 남아있는 몬스터들
int[] cur = list.get(i);
int d = Math.abs(cur[0] - N) + Math.abs(cur[1] - archer[k]); // 궁수와 몬스터 사이의 거리 계산
if (d <= D) // 사정거리 안이면
pq.add(new Monster(cur[0], cur[1], d));
}
if (!pq.isEmpty()) { // 잡을 몬스터가 있다면
Monster target = pq.poll(); // 가장 가깝고, 왼쪽에 있는 적
boolean flag = false; // 현재 타겟을 다른 궁수가 잡으려 하는지 여부 / true면 이미 다른 궁수가 잡으려 함
for (int i = 0; i < targets.size(); i++) {
int[] cur2 = targets.get(i);
if (target.x == cur2[0] && target.y == cur2[1]) // 이미 다른 누군가가 잡으려 함
flag = true;
}
if (!flag) {
targets.add(new int[] { target.x, target.y });
}
}
}
// targets 리스트에 있는 애들 전부 제거
for (int i = 0; i < targets.size(); i++) {
for (int j = list.size() - 1; j >= 0; j--) {
if (targets.get(i)[0] == list.get(j)[0] && targets.get(i)[1] == list.get(j)[1]) {
list.remove(j);
count++;
break;
}
}
}
// 남아있는 몬스터들 이동(좌표 벗어나면 삭제)
for (int i = list.size() - 1; i >= 0; i--) {
list.get(i)[0] += 1;
if (list.get(i)[0] == N)
list.remove(i);
}
}
res = Math.max(res, count);
}
}
🌟 비슷한 유형의 문제들
참고
