[코드트리 - L15] 23년 상반기 오전 1번 포탑 부수기

 

 

코딩테스트 기출 문제 설명: 포탑 부수기 | 코드트리

 

• 소요 시간 : 4시간!!

 

문제 풀이

1. 공격자 선정

2. 타겟 설정해서 레이저 공격 및 포탄 공격

3-1. 레이저 공격

3-2. 포탄 공격

4. 포탑 부서짐 및 정비

 

크게 위와 같이 나눌 수 있다.

 

1. 공격자 선정

• 0 이 아닌 값들 중 가장 약한 포탑을 공격자로 선정
• 2개 이상이면, 가장 최근 공격 포탑
• 최근 공격 포탑도 2개 이상이면, (행 + 열) 값이 가장 큰 포탑
• (행 + 열) 값도 같은게 2개 이상이면, 열이 가장 큰 포탑
• 선정 후 공격력 (N  + M)만큼 추가한다.

가장 최근 공격 포탑은 lastAttackTime 변수와 배열을 통해 공격했다면 +1을 해주어 가장 큰 값이 가장 최근 공격 포탑으로 설정했다. 

static Top pickAttack() {

	// 공격자 선정: 가장 약한 포탑
	PriorityQueue<Top> pq = new PriorityQueue<>((a, b) -> {
		if (a.power != b.power) {
			return a.power - b.power; // 오름차순
		} else if (a.lastAttackTime != b.lastAttackTime) {
			return b.lastAttackTime - a.lastAttackTime; // 내림차순
		} else if ((a.x + a.y) != (b.x + b.y)) {
			return (b.x + b.y) - (a.x + a.y); // 가장 큰 값
		}
		return b.y - a.y; // 가장 큰 값
	});

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] > 0) {
				Top t = new Top(i, j, map[i][j]);
				t.lastAttackTime = lastAttackTime[i][j];
				pq.add(t);
			}
		}
	}
	return pq.peek();
}

 

 

2. 공격할 타겟 설정

• 공격자와 반대로 우선순위를 지정한다.

	static Top pickTarget() {

		// 공격자 선정: 가장 강한 포탑
		PriorityQueue<Top> pq = new PriorityQueue<>((a, b) -> {
			if (a.power != b.power) {
				return b.power - a.power; // 가장 강한 순
			} else if (a.lastAttackTime != b.lastAttackTime) {
				return a.lastAttackTime - b.lastAttackTime; // 작은 순
			} else if ((a.x + a.y) != (b.x + b.y)) {
				return (a.x + a.y) - (b.x + b.y); // 가장 작은 값
			}
			return a.y - b.y; // 가장 작은 값
		});

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] > 0) {
					Top t = new Top(i, j, map[i][j]);
					t.lastAttackTime = lastAttackTime[i][j];
					pq.add(t);
				}
			}
		}

		return pq.peek();
	}

 

 

3. 공격

• 레이저 공격을 먼저 시행하고, 불가능할 경우 포탄 공격을 시행할 것
• 레이저 공격
  • 막혔다면 반대편으로 이동 가능하다 ex) N = 4일 때, (0, 3) -> (0, 0)
  • 공격자에서 타겟으로 가는 최단 경로로 공격하고 없으면 포탄 공격을 시행한다.
  • 최단 경로가 여러 개면 우하좌상 순으로 선택
  • 타겟은 공격력만큼 줄어들고, 경로에 존재하는 포탑들은 (공격력 / 2)만큼 줄어든다.
• 포탄 공격
  • 바로 타겟으로 폭탄이 떨어져, 타겟은 공격력만큼 줄고, 주변 8방향 또한 (공격력 / 2) 만큼 줄어든다.

 

1) 레이저 공격

• 지나온 경로를 Map에 넣어 (key, value) = (현재 경로, 이전 경로) 로 넣어 최단거리로 가능 경로만 찾아냈다.
• trace 를 통해 되돌아 가는 길이 있다면 (공격력 / 2)만큼 제거한다. 
• 그리고 추후 포탑 정비를 위해 isAttack 배열의 지나온 위치를 모두 true로 설정한다.
• 주의 할 점: target과 attack의 위치는 피해야함

	private static boolean laser(Top attack, Top target) {

		Queue<Top> queue = new ArrayDeque<>();
		queue.offer(attack);

		boolean[][] visited = new boolean[N][M];
		visited[attack.x][attack.y] = true;

		Map<String, String> route = new HashMap<>();
		route.put(attack.x + "," + attack.y, null);

		while (!queue.isEmpty()) {

			Top cur = queue.poll();
			String curKey = cur.x + "," + cur.y;

			for (int d = 0; d < 4; d++) {
				int nx = cur.x + dx[d];
				int ny = cur.y + dy[d];

				if (!isRange(nx, ny)) {
					nx = (nx + N) % N;
					ny = (ny + M) % M;
				}

				if (nx == target.x && ny == target.y) {

					String targetKey = nx + "," + ny;
					route.put(targetKey, curKey);

					// 목적지 공격
					map[nx][ny] -= attack.power;
					isAttack[nx][ny] = true;

					// 경로 공격
					String trace = targetKey;
					while (true) {
						trace = route.get(trace);
						if (trace == null)
							break;

						String[] pos = trace.split(",");
						int tx = Integer.parseInt(pos[0]);
						int ty = Integer.parseInt(pos[1]);

						if (tx == attack.x && ty == attack.y)
							continue;
						map[tx][ty] -= attack.power / 2;
						isAttack[tx][ty] = true;
					}

					return true;
				}

				// 방문 안하고 부서지지 않앗을 경우
				if (!visited[nx][ny] && map[nx][ny] > 0) {

					visited[nx][ny] = true;
					String next = nx + "," + ny;
					route.put(next, curKey);
					queue.offer(new Top(nx, ny, map[nx][ny]));

				}
			}
		}

		return false;

	}

 

 

2) 포탄 공격

• 바로 목적지로 공격하는 상황
• 8방향 체크 후, (공격력 / 2) 만큼 감소시킨 후 isAttack에 true로 변경해준다.
• 여기서 공격자의 위치랑 동일하다면 피해야 한다!!! => 이거 때문에 계속 틀렸다 정말..

	static void bomb(Top attack, Top target) {

		map[target.x][target.y] -= attack.power;
		isAttack[target.x][target.y] = true;

		// 주변 8방향 체크
		for (int d = 0; d < 8; d++) {
			int nx = target.x + dx2[d];
			int ny = target.y + dy2[d];

			if (!isRange(nx, ny)) {
				nx = (nx + N) % N;
				ny = (ny + M) % M;
			}
			
			if (nx == attack.x && ny == attack.y) continue;

			map[nx][ny] -= (int) attack.power / 2;
			isAttack[nx][ny] = true;
		}

	}

 

 

4. 포탑 부서짐 및 정비

• 부서짐은 음수인 값들을 모두 0으로 보정한다.
• 정비는 공격에 영향을 받지 않은 포탑을 모두 공격력 + 1을 진행해준다. isAttack에 false이고 > 0 이면 모두 +1을 진행해주었다.

	static void clean() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!isAttack[i][j] && map[i][j] > 0)
					map[i][j]++;
			}
		}
	}

	static void broken() {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] < 0)
					map[i][j] = 0;
			}
		}
	}

 

 

5. 그외.. 등등

그리고 이건 문제 제일 처음에 있던 조건인데, 제거했더니 런타임 에러가 발생했다. 문제를 꼼꼼히 읽는 것이 중요!

 

	static boolean isStop() {

		// 포탑이 1개가 된다면 즉시 중지
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] > 0)
					cnt++;
			}
		}

		return cnt > 1 ? false : true;
	}

 

 

다른 오류로는 target과 attack의 좌표가 계속 표시되어서, 공격자인데도 공격력만큼 감소되거나 그런 경우가 많아서 전부 예외처리 해주었다. 그리고 Top 클래스에서는 power를 (N  + M)만큼 추가해주고는, map[i][j] 에는 공격력을 추가해주지 않아 갱신이 안되는 문제도 있었다. 마찬가지로 lastAttackTime도 다음 공격 턴에서 값이 유지가 안되어서 배열을 따로 지정해 초기화 해주었다.

 

그 결과 4시간이나 걸려버림..ㅠㅠ

 

 

 

---

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static class Top {
		int x, y;
		int power;
		int lastAttackTime;

		Top(int x, int y, int power) {
			this.x = x;
			this.y = y;
			this.power = power;
		}

	}

	static int N, M, K;
	static int[][] map;
	static int[] dx = { 0, 1, 0, -1 }; // 우하좌상
	static int[] dy = { 1, 0, -1, 0 };
	static int[] dx2 = { 0, 1, 1, 1, 0, -1, -1, -1 };
	static int[] dy2 = { 1, 1, 0, -1, -1, -1, 0, 1 };
	static boolean[][] isAttack;
	static int[][] lastAttackTime;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		K = Integer.parseInt(split[2]);

		map = new int[N][M];
		lastAttackTime = new int[N][M];

		for (int i = 0; i < N; i++) {
			split = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(split[j]);
			}
		}

		int cnt = 0;
		while (K > 0) {

			K--;
			// 포탑이 1개가 된다면 즉시 중지
			if (isStop()) {
				break;
			}

			// 1. 공격자 선정
			isAttack = new boolean[N][M];
			Top attack = pickAttack();

			// 2. 공격 받을 포탑 선택
			Top target = pickTarget();
			
			// 공격력 설정
			// 공격력 상승
			map[attack.x][attack.y] += (N + M);
			attack.power = map[attack.x][attack.y];

			attack.lastAttackTime = ++cnt; // 최근 공격
			lastAttackTime[attack.x][attack.y] = cnt;

			isAttack[attack.x][attack.y] = true; // 이번 공격과 관련되어 있음

			// 3. 공격 - 레이저 or 포탄 공격
			if (!laser(attack, target)) {
				bomb(attack, target);
			}

			// 4. 포탑 부서짐
			broken();

			// 5. 포탑 정비
			clean();

		}

		int ans = -1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] > 0)
					ans = Math.max(ans, map[i][j]);
			}
		}

		System.out.println(ans);
	}

	private static void clean() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!isAttack[i][j] && map[i][j] > 0)
					map[i][j]++;
			}
		}
	}

	private static void broken() {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] < 0)
					map[i][j] = 0;
			}
		}
	}

	private static void bomb(Top attack, Top target) {

		map[target.x][target.y] -= attack.power;
		isAttack[target.x][target.y] = true;

		// 주변 8방향 체크
		for (int d = 0; d < 8; d++) {
			int nx = target.x + dx2[d];
			int ny = target.y + dy2[d];

			if (!isRange(nx, ny)) {
				nx = (nx + N) % N;
				ny = (ny + M) % M;
			}

            if (nx == attack.x && ny == attack.y) continue;

			map[nx][ny] -= (int) attack.power / 2;
			isAttack[nx][ny] = true;
		}

	}

	private static boolean laser(Top attack, Top target) {

		Queue<Top> queue = new ArrayDeque<>();
		queue.offer(attack);

		boolean[][] visited = new boolean[N][M];
		visited[attack.x][attack.y] = true;

		Map<String, String> route = new HashMap<>();
		route.put(attack.x + "," + attack.y, null);

		while (!queue.isEmpty()) {

			Top cur = queue.poll();
			String curKey = cur.x + "," + cur.y;

			for (int d = 0; d < 4; d++) {
				int nx = cur.x + dx[d];
				int ny = cur.y + dy[d];

				if (!isRange(nx, ny)) {
					nx = (nx + N) % N;
					ny = (ny + M) % M;
				}

				if (nx == target.x && ny == target.y) {

					String targetKey = nx + "," + ny;
					route.put(targetKey, curKey);

					// 목적지 공격
					map[nx][ny] -= attack.power;
					isAttack[nx][ny] = true;

					// 경로 공격
					String trace = targetKey;
					while (true) {
						trace = route.get(trace);
						if (trace == null)
							break;

						String[] pos = trace.split(",");
						int tx = Integer.parseInt(pos[0]);
						int ty = Integer.parseInt(pos[1]);

						if (tx == attack.x && ty == attack.y)
							continue;
						map[tx][ty] -= attack.power / 2;
						isAttack[tx][ty] = true;
					}

					return true;
				}

				// 방문 안하고 부서지지 않앗을 경우
				if (!visited[nx][ny] && map[nx][ny] > 0) {

					visited[nx][ny] = true;
					String next = nx + "," + ny;
					route.put(next, curKey);
					queue.offer(new Top(nx, ny, map[nx][ny]));

				}
			}
		}

		return false;

	}

	private static Top pickTarget() {

		// 공격자 선정: 가장 강한 포탑
		PriorityQueue<Top> pq = new PriorityQueue<>((a, b) -> {
			if (a.power != b.power) {
				return b.power - a.power; // 가장 강한 순
			} else if (a.lastAttackTime != b.lastAttackTime) {
				return a.lastAttackTime - b.lastAttackTime; // 작은 순
			} else if ((a.x + a.y) != (b.x + b.y)) {
				return (a.x + a.y) - (b.x + b.y); // 가장 작은 값
			}
			return a.y - b.y; // 가장 작은 값
		});

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] > 0) {
					Top t = new Top(i, j, map[i][j]);
					t.lastAttackTime = lastAttackTime[i][j];
					pq.add(t);
				}
			}
		}

		// System.out.println(pq.peek().x + " " + pq.peek().y + " " + pq.peek().power);
		return pq.peek();

	}

	private static Top pickAttack() {

		// 공격자 선정: 가장 약한 포탑
		PriorityQueue<Top> pq = new PriorityQueue<>((a, b) -> {
			if (a.power != b.power) {
				return a.power - b.power; // 오름차순
			} else if (a.lastAttackTime != b.lastAttackTime) {
				return b.lastAttackTime - a.lastAttackTime; // 내림차순
			} else if ((a.x + a.y) != (b.x + b.y)) {
				return (b.x + b.y) - (a.x + a.y); // 가장 큰 값
			}
			return b.y - a.y; // 가장 큰 값
		});

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] > 0) {
					Top t = new Top(i, j, map[i][j]);
					t.lastAttackTime = lastAttackTime[i][j];
					pq.add(t);
				}
			}
		}

		// System.out.println(pq.peek().x + " " + pq.peek().y + " " + pq.peek().power);
		return pq.peek();

	}

	static boolean isStop() {

		// 포탑이 1개가 된다면 즉시 중지
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] > 0)
					cnt++;
			}
		}

		return cnt > 1 ? false : true;
	}

	static boolean isRange(int x, int y) {
		if (x < 0 || y < 0 || x >= N || y >= M)
			return false;
		return true;
	}

}