Algorithm/Beakjoon

[JAVA] 백준 17135번 : 캐슬 디펜스

mopipi 2024. 5. 17. 15:13
반응형

https://www.acmicpc.net/problem/17135

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	static int[][] map;
	static int N, M, D, maxKill = 0;
	static List<int[]> enemies = new ArrayList<>();
	static int ivy = 0;
	
	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+1][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());
				if(map[i][j] == 1)
					enemies.add(new int[] {i, j});
			}
		}
		int[] archerPos = new int[3];
		setArcher(0, 0, archerPos);
		System.out.println(maxKill);
	}

	private static void setArcher(int idx, int cnt, int[] archerPos) {
		if(cnt == 3) {
			ivy++;
			maxKill = Math.max(maxKill, playGames(archerPos));
			return;
		}
		for (int i = idx; i < M; i++) {
			archerPos[cnt] = i;
			setArcher(idx+1, cnt+1, archerPos);
		}
		
	}
	private static List<int[]> copy(List<int[]> list) {
		List<int[]> tmp = new ArrayList<>();
		for(int[] p : list) {
			tmp.add(new int[] {p[0], p[1]});
		}
		return tmp;
	}

	private static int playGames(int[] archerPos) {
		int[][] cMap = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cMap[i][j] = map[i][j];
			}
		}
		//적 위치 복사
		List<int[]> eList = copy(enemies);
		int cnt = 0;
		//archer위치 기준으로 제거
		while(true) {
			//적 없으면 멈춤
			if(eList.isEmpty()) break;
			Set<int[]> target = new HashSet<>();
			//궁수 3명 한 명씩 돌아가며 처리
			for (int l = 0; l < 3; l++) {
				PriorityQueue<Enemy> pq = new PriorityQueue<Main.Enemy>();
				boolean[][] kill = new boolean[N][M];
				int ay = archerPos[l];
				//가능한 적들 저장
				for(int[] e : eList) {
					int dist = Math.abs(N - e[0]) + Math.abs(ay - e[1]);
					if(dist <= D)
						pq.add(new Enemy(e[0], e[1], dist));	
				}
				//제일 가까운 적 죽임
				if(!pq.isEmpty()) {
					Enemy e = pq.poll();
					if(!kill[e.x][e.y]) {
						target.add(new int[] {e.x, e.y});
						kill[e.x][e.y] = true; 
					}
				}
			}
			//3명의 목표물 삭제
			int k = 0;
			for(int[] t : target) {
				//System.out.printf("<<%d %d>> x : %d, y: %d\n",ivy, k++, t[0], t[1]);
				for (int i = eList.size()-1; i >= 0; i--) {
					if(t[0] == eList.get(i)[0] && t[1] == eList.get(i)[1]) {
						eList.remove(i);
						cnt++;
						break;
					}
				}
			}
			//한 칸 이동
			for (int i = eList.size()-1; i >= 0; i--) {
				eList.get(i)[0] += 1;
				if(eList.get(i)[0] == N) 
					eList.remove(i);
			}
		}
		return cnt;
	}
	

	private static class Enemy implements Comparable<Enemy>{
		int x, y;
		int dist;
		
		Enemy(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
		
		@Override
		public int compareTo(Enemy o) {
			if(this.dist == o.dist)
				return this.y - o.y;
			return this.dist - o.dist;
		}
	}
}

💡 백트레킹(조합), 시뮬레이션, 구현

풀이

 

푸는데 진빠지는 문제,,, 조건이 까다롭고 좌표 다룰 때 중복 처리랑 제거가 어려웠다.

문제는 아래와 같은 방식으로 풀이가 진행된다.

  1. 처음 map 정보를 저장할 때, 적의 위치를 int[] 배열 형태로 저장 (얘네만 고려하면 됨)
  2. 조합(백트레킹)을 사용해 궁수 3명의 위치를 배열에 저장하고, 그것을 토대로 시뮬레이션을 돌린다.
    • 이때 궁수의 위치의 x좌표는 어차피 N+1(map에선 N)로 동일하기 때문에 1차원 배열에 y  좌표 위치만 저장
  3. 시뮬레이션을 돌릴 때, 적군 위치 리스트 먼저 복사한 뒤, 궁수 3명에 대해 각각 제일 가까운 적 위치 저장 
    • 제일 가까운 적은 거리(dist)가 가까운 순서, 거리가 같다면 y값이 작은 순서대로 오름차순 정렬 
    • 그러므로 영향권 내 모든 적들의 위치를 우선순위 큐에 저장한 뒤, 해당 조건을 기준으로 정렬함
    • 적 위치 저장 끝나면, 제일 가까운 적 한명
  4. 궁수 3명에 대해 각각 다 구했으면, 그 target 안 적군들을 리스트에서 삭제 후, 나머지 적군은 한 칸씩 전진
    • 배열은 set에 넣어도 중복처리가 안되므로 boolean[][]배열을 자체적으로 만들어 중복 방지 해줌
    • 남은 적군 List를 순회하며, 판 밖으로 나온 적들은 삭제함
      • 이때, List를 순회 + 제거를 함께 해야 하므로 뒤에서부터 진행함 (idx 에러 방지)
Set<int[]>가 중복 제거가 안되는 이유
 기시감이 든다 했더니 전에도 비슷한걸로 틀림..ㅋ.ㅋ ... 
- Set의 중복확인 방법 : equals( ), hashCode( ) 메서드를 사용한다.
   -> 이때 배열은 equals( ), hashCode( )가 배열의 내용이 아닌 객체의 참조를 기반으로 동작한다
즉, 배열에 아무리 같은 값이 들어있다고 해도, 그 배열의 메모리 주소를 비교하므로 다른 취급함!
- 객체도 당연히 마찬가지....
- 그렇기에 Set을 이용할 때 boolean 배열을 사용해 중복인지 별도로 체크해줬다.
- Set의 기능을 이용하고 싶다면?
   1) int[] 배열 대신 List로 정의한다 (List는 중복 구분함)
   2) 배열을 사용자 정의 객체로 감싸서 equals( ), hashCode( ) 메서드를 재정의해줌
반응형