백준 17135번: 캐슬 디펜스

문제 설명

• 주어진 조건대로 코드를 작성하는 시뮬레이션 문제입니다.

접근법

• 접근법은 코드주석과 틀렸던 부분에서 자세히 설명하겠습니다.

정답

import java.util.*;

public class Main {
	static int N, M, D;
	static int[][] original_board;
	static int[] answer = new int[3];
	static int max_score = Integer.MIN_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		D = sc.nextInt();
		original_board = new int[N][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				original_board[i][j] = sc.nextInt();
			}
		}

		comb(0, 0);
		System.out.println(max_score);

	}

	public static void comb(int depth, int start) {
		if (depth == 3) {
			// 궁수의 배치가 다를때마다 새로운 board판을 사용해야 합니다.
			int[][] board = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					board[i][j] = original_board[i][j];
				}
			}
			// 궁수의 위치를 담습니다.
			List<pos> archers = new ArrayList<pos>();
			for (int i = 0; i < answer.length; i++) {
				archers.add(new pos(N, answer[i]));
			}
			
			int score = 0; // 이번 배치에서의 점수를 나타냅니다.
			// System.out.println("archers_pos "+archers.toString());
			for (int t = 0; t < N; t++) { // t는 턴을 의미합니다.
				TreeSet<pos> archers_target = new TreeSet<pos>(); // 궁수는 동시에 쏘기 때문에 동일한 적을 쏠 수도 있습니다.(그래서 Set을 사용했습니다)
				// System.out.println("turn"+t);
				for (int a = 0; a < archers.size(); a++) { // 각 턴마다 궁수가 쏠 적을 선정합니다.
					// System.out.println("archer"+a);
					int x = Integer.MAX_VALUE;
					int y = Integer.MAX_VALUE;
					int min_d = Integer.MAX_VALUE;
					for (int i = 0; i < N - t; i++) { // 행: 턴이 지나면 적이 아래로 이동하기 때문에 N-t까지의 적만 쏠 수 있습니다.
						for (int j = 0; j < M; j++) { // 열: 열은 특별한 제한이 없습니다.
							if (board[i][j] != 1) continue; // 적이 아니면 pass합니다.
							int d = distance(archers.get(a).x, archers.get(a).y, i + t, j); // 궁수와 적의 거리를 계산합니다. 이 때 t턴의 적은 t만큼 가까이 와 있기 때문에 i+t를 넣는 걸 주의합니다.
							if (d <= D && (min_d > d || (min_d == d && y > j))) { // 궁수의 범위에 들어와야 합니다 and (더 가까운 적 or 동일한 거리면 왼쪽에 있는 적)을 선택합니다
								// 쏠 적의 위치를 갱신해 줍니다.
								x = i;
								y = j;
								min_d = d;
								// System.out.println(x+"||"+y+"||"+min_d);
							}
						}
					}
					if (y == Integer.MAX_VALUE) continue; // 궁수가 아무런 적도 쏘지 않는 상황입니다.
					archers_target.add(new pos(x, y)); // 최종적으로 궁수가 쏠 적의 위치를 set에 넣습니다. 궁수끼리 타겟이 중복될 수 있기 때문에 여기서 적을 죽이지 않고 for문을 나가서 한꺼번에 쏩니다.
				}
				// System.out.println("targets_pos "+archers_target.toString());
				int size = archers_target.size(); // poll을 하기 때문에 size값이 달라집니다. 그래서 size변수를 생성했습니다.
				for (int i = 0; i < size; i++) { // 적을 죽입니다. 
					pos temp = archers_target.pollFirst();
					board[temp.x][temp.y] = 0;
					score++;
				}
//				for (int i = 0; i < N; i++) {
//					System.out.println(Arrays.toString(board[i]));
//				}
			}
			max_score = Math.max(score, max_score);
//			System.out.println(archers.toString());
			return;
		}
		for (int i = start; i < M; i++) {
			answer[depth] = i;
			comb(depth + 1, i + 1);
		}
	}

	public static int distance(int arc_x, int arc_y, int enem_x, int enem_y) {

		return Math.abs(arc_x - enem_x) + Math.abs(arc_y - enem_y);
	}

	static class pos implements Comparable<pos> { // TreeSet에 넣기 위해 Comparable을 구현해야 합니다.
		int x;
		int y;

		public pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "pos [x=" + x + ", y=" + y + "]";
		}

		@Override
		public int compareTo(pos o) {
			// TODO Auto-generated method stub
			return (this.x != o.x) ? this.x - o.x : this.y - o.y; // x값과 y값에 대한 비교를 모두 해야 합니다.
		}

	}
}

기타

• 중간에 꼬이기 시작하니 걷잡을 수 없이 문제가 발생했다.
  • 이런 상황이 안나오는게 가장 중요.
    • 중간중간 print찍어서 잘 나오는지 확인하기!
  • 그게 아니라면 처음부터 다시 설계하자.

놓쳤던 부분들

• 적이 전진하기 때문에 좌표를 t만큼 더해줘야 한다.
• Treeset에 넣기 위해 Comparable을 구현해야 한다.
  • x에 대한 비교만 하면 안된다.
    • y에 대한 비교가 없으면(4,1)과 (4,2)도 같은값으로 인식하고 하나만 남긴다.
• 궁수가 동일한 적을 쏠 수도 있다.
  • 모든 궁수의 선택이 끝난 뒤 적을 쏴야한다.
• 조합마다 다른 결과를 얻어야 하기 때문에 전역변수 original_board에 모든 값을 덮어쓰면 안된다.