[코드트리] 포탑 부수기 - Java (삼성SW역량테스트 2023 상반기 오전 1번)

🔗 문제

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

 

👨🏻‍💻 풀이 및 코드

문제 유형 및 난이도 : BFS / G1

풀이

느낀 점

코드가 길어서 어디서 틀렸는지 찾는게 힘들었다.. 해결하는데 5시간?넘게 걸린 것 같다. 

 

틀린 부분

1. 시점 k를 time++로 처리
2. bomb에서 이미 공격받은 자리는 공격하면 안됨 (가장 자리에서 막히면 반대편으로 돌아오기 때문에 겹칠 수 있다)
3. 다시 포탑 list를 넣을 때 새로 Turret 객체를 생성해서 넣으면 안 된다. map[i][j] 로 넣어야 한다. 새로 객체를 만들어서 넣으려면 map[i][j] 에도 넣어야 한다. (아래 이번에 알게 된 점 2번과 같은 이유)

이번에 알게 된 점

1. bfs 할 때 경로 찾는 방법
2. 객체를 생성하고 2차원 배열(map)과 list 에 각각 넣은 후 list 에서 객체를 빼서 값을 수정하면 map 객체의 값도 변경된다. (Call by Value vs Call by Reference)

---

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int N, M;
	static List<Turret> turrets;
	static Turret[][] map;
	static boolean[][] effected;
	
	static class Turret implements Comparable<Turret>{
		int power;
		int x; 
		int y;
		int time;
		
		public Turret(int power, int x, int y, int time) {
			this.power = power;
			this.x = x;
			this.y = y;
			this.time = time;
		}
		
		@Override
		public int compareTo(Turret o) {
			if(this.power == o.power) {
				if(this.time == o.time) {
					int sum1 = this.x+this.y;
					int sum2 = o.x+o.y;
					
					if(sum1 == sum2) {
						// 큰거
						return o.y - this.y;
					}
					
					// 큰거
					return sum2 - sum1;
				}
				
				// 큰거
				return o.time - this.time;
			}
			
			// 작은거
			return this.power - o.power;
		}
	}
	
    public static void main(String[] args) throws Exception {
//    	System.setIn(new FileInputStream("res/input_ct_포탑부수기.txt"));
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	int K = Integer.parseInt(st.nextToken());
    	
    	turrets = new ArrayList<>();
    	map = new Turret[N][M];
    	effected = new boolean[N][M];
    	
    	int power;
    	for(int i=0; i<N; i++) {
    		st = new StringTokenizer(br.readLine(), " ");
    		for(int j=0; j<M; j++) {
    			power = Integer.parseInt(st.nextToken());
    			Turret turret = new Turret(power, i, j, 0);
    			map[i][j] = turret;
    			if(power > 0) {
    				turrets.add(turret);
    			}
    		}
    	}
    	
    	Collections.sort(turrets);
    	
    	for(int k=1; k<=K; k++) {
    		if(turrets.size() == 1) break;
    		
    		Turret weakest = turrets.get(0);
    		weakest.power += N+M;
    		weakest.time = k;
    		effected[weakest.x][weakest.y] = true; 
    		
    		Turret strongest = turrets.get(turrets.size()-1);
    		effected[strongest.x][strongest.y] = true;
    		
    		if(!bfs(weakest, strongest)) {
    			bomb(weakest, strongest);		// 폭탄
    		}
    		
    		setting();
    		
    	}
    	
    	System.out.println(turrets.get(turrets.size()-1).power);
    }
    
    static int[] dx = {0, 1, 0, -1, -1, 1, 1, -1}; //우/하/좌/상/대각선4방
    static int[] dy = {1, 0, -1, 0, 1, 1, -1, -1};
    
    static boolean bfs(Turret weakest, Turret strongest) {
    	Queue<int[]> que = new ArrayDeque<>();
    	boolean[][] visited = new boolean[N][M];
    	int x = weakest.x;
    	int y = weakest.y;
    	visited[x][y] = true;
    	que.add(new int[] {x, y});
    	
    	while(!que.isEmpty()) {
    		int[] now = que.poll();
    		
    		for(int d=0; d<4; d++) {
    			int nx = checkX(now[0] + dx[d]);
    			int ny = checkY(now[1] + dy[d]);
    			
    			if(nx == strongest.x && ny == strongest.y) {	//목적 포탑
    				//laser
    				strongest.power = Math.max(0, strongest.power - weakest.power);
    				
    				int px = x, py = y, power=weakest.power/2;
    				for(int a=2; a<now.length; a++) {	// 경로
    					px = checkX(px + dx[now[a]]);
    					py = checkY(py + dy[now[a]]);
    					
    					map[px][py].power = Math.max(0, map[px][py].power-power);
    					effected[px][py] = true;
    				}
    				return true;
    			}
    			
    			if(map[nx][ny].power == 0 || visited[nx][ny]) continue;
    			int[] tmp = new int[now.length+1];	// 방향 추기 하기 위해 사이즈 1 증가
    			for(int a=2; a<now.length; a++) {	// 기존 경로 삽입
    				tmp[a] = now[a];
    			}
    			tmp[0] = nx;
    			tmp[1] = ny;
    			tmp[tmp.length-1] = d;		// 현재 방향 추가
    			que.add(tmp);
    			visited[nx][ny] = true;
    		}
    	}
    	
    	return false;
    }
    

    static int checkX(int x) {
    	if(x<0) x=N-1;
    	if(x>=N) x=0;
    	return x;
    }
    
    static int checkY(int y) {
    	if(y<0) y=M-1;
    	if(y>=M) y=0;
    	return y;
    }
    
    static void bomb(Turret weakest, Turret strongest) {
    	int sx = strongest.x, sy = strongest.y;
    	strongest.power = Math.max(0, strongest.power - weakest.power);
    	
    	int power = weakest.power/2;
    	for(int d=0; d<8; d++) {
    		int nx = checkX(sx + dx[d]);
    		int ny = checkY(sy + dy[d]);
    		
    		if(effected[nx][ny]) continue;
    		map[nx][ny].power = Math.max(0, map[nx][ny].power-power);
    		effected[nx][ny] = true;
    	}
    }
    
    static void setting() {
    	turrets.clear();
    	
    	for(int i=0; i<N; i++) {
    		for(int j=0; j<M; j++) {
    			if(map[i][j].power == 0) continue;
    			if(effected[i][j]) {	
    				effected[i][j] = false;	// 원상복구
    			} else {
    				map[i][j].power += 1;
    			}
    			
    			turrets.add(map[i][j]);		// map에 들어있는 객체로 넣어야 한다. 아래 처럼 바뀌면 안됨.
//    			turrets.add(new Turret(map[i][j].power, i, j, map[i][j].time));
    		}
    	}
    	
    	Collections.sort(turrets);
    }
    
}