알고리즘/코드트리

포탑 부수기[G1]

블랑v 2024. 10. 6. 02:56

 

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

 

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

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 

2트만에 성공

주요 쟁점은 배열 대신 Tower 객체를 사용하는 것.

그리고 Compable과 핸디캡 쪽 순서 처리.

 

 

import java.util.*;
import java.io.*;
class Main {
	static int N, M, K;
	static Tower[][] map;
	static List<Tower> towers = new ArrayList<>();
	//우/하/좌/상
	static int[] DR = {0, 1, 0, -1};
	static int[] DC = {1, 0, -1, 0};
	static int[] NR = {-1, -1, -1, 0, 0 ,1, 1, 1};
	static int[] NC = {-1,0, 1, -1, 1, -1, 0, 1};
	
	public static void main(String[] args) {
		input();
		solve();
		cal();
	}
	
	static void log(String msg) {
		System.out.println("===========================" + msg);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				System.out.print(map[i][j].dmg + " ");
			}
			System.out.println();
		}
		System.out.println("===========================");
	}
	
	static void cal() {
		int res = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				res = Math.max(res, map[i][j].dmg);
			}
		}
		System.out.println(res);
	}
	
	static void solve() {
		for(int i = 0; i < K; i++) {
//			log(i + 1 + "round start");
			setTowers();
			if(towers.size() < 2) return; //부서지지 않은 포탑이 1개가 된다면 그 즉시 중지
			
			//공격자 선정
			Tower atkTower = Collections.min(towers);
			atkTower.attacked = true;
			atkTower.recent = i + 1;
			Tower defTower = Collections.max(towers);
			defTower.attacked = true;
			//핸디캡
			atkTower.dmg += (N + M); 
			//공격
			List<int[]> laserPath = tryLaserAtk(atkTower, defTower); //레이져 공격 시도
			if(laserPath.isEmpty()) tryBomb(atkTower, defTower);
			else checkLaserDamage(atkTower, defTower, laserPath);
			
			//포탑 부서짐 및 정비
			brokenAndRepair();
			
//			log(i + 1 + "round end");
		}
	}
	
	static void brokenAndRepair() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				Tower tower = map[i][j];
				if(tower.dmg == 0) continue;
				if(tower.attacked) tower.attacked = false;
				else tower.dmg += 1;
			}
		}
	}
	
 	static void tryBomb(Tower atkTower, Tower defTower) {
 		int damage = atkTower.dmg;
		int r = defTower.r;
		int c = defTower.c;
		//공격 대상
		defTower.dmg = Math.max(0, defTower.dmg - damage);
		
		//8방
		for(int i = 0; i < 8; i++) {
			int nr = checkOutOfMap(r + NR[i], N);
			int nc = checkOutOfMap(c + NC[i], M);
			if(atkTower.r == nr && atkTower.c == nc) continue;
			
			Tower tower = map[nr][nc];
			tower.attacked = true;
			tower.dmg = Math.max(0, tower.dmg - (damage / 2));
		}
	}
	
	static void checkLaserDamage(Tower atkTower, Tower defTower, List<int[]> laserPath) {
		int damage = atkTower.dmg;
		//처음, 마지막은 제외(시작과 끝)
		for(int i = 1; i < laserPath.size() - 1; i++) {
			int[] now = laserPath.get(i);
			int r = now[0];
			int c = now[1];
			
			Tower tower = map[r][c];
			tower.attacked = true;
			tower.dmg = Math.max(0, tower.dmg - (damage / 2));
		}
		
		//마지막
		defTower.dmg = Math.max(0, defTower.dmg - damage);
	}
	
	static List<int[]> tryLaserAtk(Tower atkTower, Tower defTower) {
		boolean[][] check = new boolean[N][M];
		Queue<Trace> bfs = new ArrayDeque<>();
		bfs.add(new Trace(atkTower.r, atkTower.c));
		
		//목표
		int resR = defTower.r;
		int resC = defTower.c;
		List<int[]> traceLine = new ArrayList<>(); //레이져 경로
		
		while(!bfs.isEmpty()) {
			Trace trace = bfs.poll();
			int r = trace.r;
			int c = trace.c;
			List<int[]> line = trace.line;
			if(check[r][c] || map[r][c].dmg <= 0) continue;
			check[r][c] = true;
			line.add(new int[] {r, c});
			
			if(r == resR && c == resC) {
				traceLine = line;
				break;
			}
			
			for(int i = 0; i < 4; i++) {
				int nr = checkOutOfMap(r + DR[i], N);
				int nc = checkOutOfMap(c + DC[i], M);
				if(check[nr][nc]) continue;
				Trace next = new Trace(nr, nc);
				for(int j = 0; j < line.size(); j++) {
					int[] copy = line.get(j);
					next.line.add(new int[] {copy[0], copy[1]});
				}
				
				bfs.add(next);
			}
		}
		
		return traceLine;
	}
	
	static void setTowers() {
		towers.clear();
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j].dmg == 0) continue;
				towers.add(map[i][j]);
			}
		}
	}
	
	
	static int checkOutOfMap(int num, int len) {
		num %= len;
		if(num < 0) num += len;
		return num;
	}
	
	static boolean cantGo(int r, int c) {
		return r < 0 || c < 0 || r >= N || c >= M;
	}
	
	static void input() {
		try {
			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];
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0; j < M; j++) {
					int dmg = Integer.parseInt(st.nextToken());
					map[i][j] = new Tower(i, j, dmg, 0);
				}
			}
			
		} catch(IOException e) {
			
		}
	}
}

class Tower implements Comparable<Tower>{
	Integer r, c, dmg, recent;
	boolean attacked = false;

	@Override
	public int compareTo(Tower t) {
	
	    if (!this.dmg.equals(t.dmg)) {
	        return Integer.compare(this.dmg, t.dmg);
	    }
	    
	    if (!this.recent.equals(t.recent)) {
	        return Integer.compare(t.recent, this.recent);
	    }
	    
	    int thisSum = this.r + this.c;
	    int tSum = t.r + t.c;
	    if (thisSum != tSum) {
	        return Integer.compare(tSum, thisSum);
	    }
	    
	    return Integer.compare(t.c, this.c);
	}
	
	public Tower(int r, int c, int dmg, int recent) {
		this.r = r;
		this.c = c;
		this.dmg = dmg;
		this.recent = recent;
	}

}

class Trace {
	int r, c;
	List<int[]> line = new ArrayList<>();
	public Trace(int r, int c) {
		this.r = r;
		this.c = c;
	}
}