[알고리즘][X] 포탑 부수기

https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	/**
	 * 
	 '공격력'에 따라 포탑을 구할 수 있어야한다.
	 '가장 최근'인지도 확인해야한다
	 '행과 열의 합'도 확인해야한다
	 '열 값'도 확인해야한다.
	 - > 이 속성들을 가진 객체 만들어줌
	 공격자로 선정되면 N + M만큼 상승
	 */
	static class Turret implements Comparable<Turret>{
		int attk;
		int recent;
		int r;
		int c;
		boolean isBroken;
		public Turret(int attk, int recent, int r, int c, boolean isBroken) {
			super();
			this.attk = attk;
			this.recent = recent;
			this.r = r;
			this.c = c;
			this.isBroken = isBroken;
		}
		
		@Override
		public int compareTo(Turret o) {
			if (attk != o.attk) return attk - o.attk;
			if (recent != o.recent) return o.recent - recent;
			if ((r + c) != (o.r + o.c)) return (o.r + o.c) - (r + c);
			return o.c - c;
		}

		@Override
		public String toString() {
			return "Turret [attk=" + attk + ", recent=" + recent + ", r=" + r + ", c=" + c + ", isBroken=" + isBroken
					+ "]";
		}
	}
	
	static class Node {
		Point point;
		List<Point> history;
		public Node(Point point, List<Point> history) {
			super();
			this.point = point;
			this.history = history;
		}
		
	}
	
	static int N;
	static int M;
	static int K;
	static Turret[][] map;
	static List<Point> histories;
	static List<Turret> sortedTurret;
	 
	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());
		K = Integer.parseInt(st.nextToken());
		
		boolean[][] isRelatedAttack = new boolean[N][M];
		sortedTurret = new ArrayList<>();
		map = new Turret[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int attk = Integer.parseInt(st.nextToken());
				Turret turret;
				if (attk == 0) {
					turret = new Turret(attk, 0, i, j, true);
				} else {					
					turret = new Turret(attk, 0, i, j, false);
					sortedTurret.add(turret);
				}
				map[i][j] = turret;
			}
		}
		
		for (int k = 1; k <= K; k++) {
//			System.out.println(k);
//			System.out.println("BEFORE");
//			print();
			// 포탑 정렬
			Collections.sort(sortedTurret);
//			print();
//			printBoolean();
//			printTurrets();
			// 포탑이 하나만 남으면 중지
			if (sortedTurret.size() == 1) {
				break;
			}
			
		// 공격자 선정
		/**
		 * 
		 '공격력'에 따라 포탑을 구할 수 있어야한다.
		 '가장 최근'인지도 확인해야한다
		 '행과 열의 합'도 확인해야한다
		 '열 값'도 확인해야한다.
		 - > 이 속성들을 가진 객체 만들어줌
		 공격자로 선정되면 N + M만큼 상승
		 */
		
		// 공격자 선정을 위한 트리셋 (앞뒤에서 접근이 가능해야하므로)
			// 트리셋 쓰면 갱신이 안되므로 정렬 해줌
		// 공격자 공격을 위한 좌표 -> 터렛 객체 
		// 누가 공격과 무관한지를 알 수 있는 좌표 -> boolean
			Turret attkTurret = sortedTurret.get(0);
//			System.out.println("attack");
			
			attkTurret.recent = k;
			// 공격력 증가
			attkTurret.attk += N + M;
//			System.out.println(attkTurret);
		
			
		// 공격자 공격
		/**
		 * 1. 레이저
		 * ㄱ. 상하좌우
		 * ㄴ. 부서진 포탑은 못 지나감
		 * ㄷ. 가장자리를 지나가면 반대편이 나옴
		 * 
		 * 공격자 위치에서 공격 대상까지 최단 경로가 존재하지 않으면 포탄 공격
		 * 최단 경로가 2개 이상이면 우/하/좌/상 순으로 먼저 움직인 경로가 선택됨
		 * 경로에 있는 포탑은 50%, 공격 대상 포탑은 100%
		 * 
		 * 2. 포탄 공격
		 * ㄱ. 그 지점에 포탄 바로 투하
		 * ㄴ. 8방 이웃 50%, 공격 대상 포탑 100%
		 * ㄷ. 가장자리인 경우 반대편도 고려
		 * 
		 */
		
			// 공격 대상 선정
			Turret attacked = sortedTurret.get(sortedTurret.size()-1);
//			System.out.println("attacked");
//			System.out.println(attacked);
			isRelatedAttack = new boolean[N][M];
			isRelatedAttack[attkTurret.r][attkTurret.c] = true;
		// 1. 레이저
			histories = new ArrayList<>();
			boolean flag = bfs(new Point(attkTurret.r, attkTurret.c), new Point(attacked.r, attacked.c));
			if (flag) { // 레이저 공격 가능
//				System.out.println("LASER");
				for (Point point : histories) {
//					System.out.println(point);
					if (point.equals(new Point(attacked.r, attacked.c))) {
						map[point.x][point.y].attk -= attkTurret.attk;
						isRelatedAttack[point.x][point.y] = true;
					} else {
						map[point.x][point.y].attk -= attkTurret.attk / 2;
						isRelatedAttack[point.x][point.y] = true;
					}
				}
			} else { // 레이저 불가능 = 포탄 공격
//				System.out.println("BOMB");
				int[] dx = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
				int[] dy = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
				
				for (int i = 0; i < 9; i++) {
					int nx = attacked.r + dx[i];
					int ny = attacked.c + dy[i];
					
					
					
					Point converted = convert(nx, ny);
					nx = converted.x;
					ny = converted.y;
					
					if (nx == attkTurret.r && ny == attkTurret.c) {
//						System.out.println(nx + " " + ny);
						continue;
					}
					
					if (!map[nx][ny].isBroken) {						
						if (nx == attacked.r && ny == attacked.c) {
							map[nx][ny].attk -= attkTurret.attk;
							isRelatedAttack[nx][ny] = true;
						} else {
							map[nx][ny].attk -= attkTurret.attk / 2;
							isRelatedAttack[nx][ny] = true;
						}
					}
				}
			}

		// 포탑 부서짐
		/**
		 * 공격력이 0 이하가 되면 포탑 부서짐
		 */
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (!map[i][j].isBroken) {
						if (map[i][j].attk <= 0) {
							map[i][j].isBroken = true;
							sortedTurret.remove(map[i][j]);
						}
					}
				}
			}
		// 포탑 정비
		/**
		 * 부서지지 않은 포탑 중 공격과 무관했던 포탑 공격력 1씩 올라감
		 * 즉, 공격자도 아니고, 공격에 피해를 입은 포탑도 아닌 경우
		 */
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (!map[i][j].isBroken) {
						if (!isRelatedAttack[i][j]) {
							map[i][j].attk++;
						}
					}
				}
			}
			
//			System.out.println("AFTER");
//			print();
		}
		
		Collections.sort(sortedTurret);
//		print();
		System.out.println(sortedTurret.get(sortedTurret.size()-1).attk);
	}

	private static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j].attk + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	private static void printBoolean() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j].isBroken + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	private static void printTurrets() {
		for (Turret turret : sortedTurret) {
			System.out.println(turret);
		}
		System.out.println();
	}
	
	

	private static boolean bfs(Point start, Point end) {
		// 우하좌상 순
		int[] dx = {0, 1, 0, -1};
		int[] dy = {1, 0, -1, 0};
		
		boolean[][] visited = new boolean[N][M];
		Queue<Node> queue = new ArrayDeque<>();
		queue.add(new Node(start, new ArrayList<>()));
		visited[start.x][start.y] = true;
		while (!queue.isEmpty()) {
			Node curNode = queue.poll();
			int x = curNode.point.x;
			int y = curNode.point.y;
			
			if (x == end.x && y == end.y) {
				histories = curNode.history;
				return true;
			}
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				Point converted = convert(nx, ny);
				nx = converted.x;
				ny = converted.y;
				List<Point> history = new ArrayList<>();
				if (!visited[nx][ny] && !map[nx][ny].isBroken) {
//					System.out.println(nx + " " + ny);
					visited[nx][ny] = true;
					history.addAll(curNode.history);					
					history.add(new Point(nx, ny));
					queue.add(new Node(new Point(nx, ny),  history));
				}
			}
		}
		return false;
	}

	private static Point convert(int nx, int ny) {
		int rnx;
		if (0 <= nx && nx < N) {
			rnx = nx;
		} else if (nx < 0) {
			rnx = N - 1;
		} else { // (nx >= N)
			rnx = 0;
		}
		int rny;
		if (0 <= ny && ny < M) {
			rny = ny;
		} else if (ny < 0) {
			rny = M - 1;
		} else { //(nx >= M)
			rny = 0;
		}
		
		return new Point(rnx, rny);
	}
}

나의 풀이

- " 공격자는 해당 공격에 영향을 받지 않습니다.": 이 문구를 되게 당연하게 여기고 넘겼다. 하지만 이는 의미가 있는 것이었고 구현을 하지 않았고 그래서 틀렸다.

- 사소한 문제라도 무조건 꼼꼼하게 보자!!!!