[코드트리] 포탑 부수기 - JAVA

📖 문제

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

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

 

🔧 풀이법

기본 시뮬레이션 문제이다.

bfs를 돌릴 때 경로를 저장하는 것이 포인트!

 

1. towerList와 tCnt를 사용해서 공격할 수 있는 포탑을 관리함

2. bfs를 사용해서 laser 공격을 구현함. Point[][] route 배열을 생성해서 경로를 저장할 수 있도록 하였다!

 

✏️ 소감

bomb() 함수에서.. 변수 오타를 내서 디버깅하는데 한참 걸렸다..... 땋..

 

 

🖥️ 코드

package codetree;

import java.io.BufferedReader;
import java.io.IOException;
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 Codetree_포탑부수기 {
	static class Point {
		int x, y;

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

		@Override
		public String toString() {
			return "Point [x=" + x + ", y=" + y + "]";
		}
		
	}
	
	static class Tower implements Comparable<Tower> {
		int x, y;
		int power;
		int time;
		
		public Tower(int x, int y, int power, int time) {
			super();
			this.x = x;
			this.y = y;
			this.power = power;
			this.time = time;
		}

		@Override
		public int compareTo(Tower o) {
			if(this.power != o.power) return this.power - o.power;
			if(this.time != o.time) return o.time - this.time;
			if((this.x+this.y) != (o.x + o.y)) return (o.x + o.y) - (this.x + this.y);
			return o.y - this.y;
		}
		
	}
	
	static int N, M, K;
	static Tower[][] map;
	static boolean[][] visited;
	static boolean[][] isAttacked;
	static int tCnt; 		// 남은 포탑 개수
	static List<Tower> towerList;
	static Point[][] route;
	static int[] dx = {0, 1, 0, -1};	// 우, 하, 좌, 상
	static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) throws IOException {
		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());
		
		map = new Tower[N][M];
		towerList = new ArrayList<>();
		
		// 타워
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				int power = Integer.parseInt(st.nextToken());
				map[i][j] = new Tower(i, j, power, 0);
			}
		}
		
		// 시뮬
		for(int turn=1; turn<=K; turn++) {
			// 남은 포탑이 1개면 즉시 중단
			
			init();
			
			if(tCnt <= 1) break;
			
			sortTower();
			
			// 1. 공격자 선정
			Tower start = getAttack();
			start.power += (N+M);	// 공격력 강화
			start.time = turn;
			
			// 2. 공격대상 선정
			Tower target = getTarget();
		
			// 3. 공격
			isAttacked = new boolean[N][M];
			isAttacked[start.x][start.y] = true;
			isAttacked[target.x][target.y] = true;
			
			if(!laser(start, target)) {
				bomb(start, target);
			}
			
			// 4. 포탑 부서짐
			breakTower();
		
			// 5. 포탑 정비
			fixTower();
			
		}
		
		// 결과 출력
		int max = Integer.MIN_VALUE;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				max = Math.max(map[i][j].power, max);
			}
		}
		
		System.out.println(max);
	}
	
	public static void init() {
		tCnt = 0;
		towerList.clear();
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j].power > 0) {
					towerList.add(map[i][j]);
					tCnt++;
				}
			}
		}
	}
	
	public static Tower getAttack() {
		return towerList.get(0);
	}
	
	public static Tower getTarget() {
		return towerList.get(tCnt-1);
	}
	
	public static void sortTower() {
		Collections.sort(towerList);
	}
	
	public static boolean laser(Tower start, Tower target) {
		boolean flag = false;
		Queue<Point> q = new ArrayDeque<>();
		visited = new boolean[N][M];
		route = new Point[N][M];
		
		q.offer(new Point(start.x, start.y));
		visited[start.x][start.y] = true;
		
		Point cur;
		
		while(!q.isEmpty()) {
			cur = q.poll();
			
			// target에 도착했을 때
			if(cur.x == target.x && cur.y == target.y) {
				flag = true;
				break;
			}
			
			for(int i=0; i<4; i++) {
				int nx = (cur.x + dx[i] + N) % N;
				int ny = (cur.y + dy[i] + M) % M;
				
				if(map[nx][ny].power == 0 || visited[nx][ny]) continue;
				
				route[nx][ny] = new Point(cur.x, cur.y);
				q.offer(new Point(nx, ny));
				visited[nx][ny] = true;
			}
		}
		
		if(flag) {
			// 레이저 공격
			// 1. target 공격
			map[target.x][target.y].power -= start.power;
			
			// 2. 경로에 있는 포탑 공격
			cur = route[target.x][target.y];
			int p = start.power/2;
			while(cur.x != start.x || cur.y != start.y) {
				isAttacked[cur.x][cur.y] = true;
				map[cur.x][cur.y].power -= p;
				cur = route[cur.x][cur.y];
			}
		}
		
		return flag;
	}
	
	public static void bomb(Tower start, Tower target) {
		int[] tx = {0, 0, -1, -1, -1, 1, 1, 1};
		int[] ty = {-1, 1, -1, 0, 1, -1, 0, 1};
		
		target.power -= start.power;
		int p = start.power / 2;
		
		for(int i=0; i<8; i++) {
			int nx = (target.x + tx[i] + N) % N;
			int ny = (target.y + ty[i] + M) % M;
			
			if(map[nx][ny].power == 0) continue;
			if(nx == start.x && ny == start.y) continue;	
			
			isAttacked[nx][ny] = true;
			map[nx][ny].power -= p;
		}
	}
	
	public static void breakTower() {
		tCnt = 0;
		towerList.clear();
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j].power < 0) {
					map[i][j].power = 0;
				}
			}
		}
	}
	
	public static void fixTower() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j].power == 0 || isAttacked[i][j]) continue;
				map[i][j].power++;
			}
		}
	}
	
	// 디버깅용
	public static void print() {
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				sb.append(map[i][j].power + " ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
}