[코드트리] 포탑 부수기

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

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

[코드]

import java.util.*;

class Node_포탑부수기 {
	int x,y;
	
	public Node_포탑부수기 (int x, int y) {
		this.x=x;
		this.y=y;
	}
}


public class 포탑부수기 {
	static int n,m,k;
	static int[][] arr;
	static int[][] lastAttack; // 공격 시점 저장 배열
	static boolean[][] isAttacked; // 공격 관련 여부 체크 배열
	static int[] dx= {0,1,0,-1};
	static int[] dy= {1,0,-1,0};
	static int[] ddx={0,1,0,-1,1,1,-1,-1}; // bomb 공격 위한 상하좌우, 대각선
	static int[] ddy={1,0,-1,0,-1,1,-1,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		m=sc.nextInt();
		k=sc.nextInt();
		
		arr=new int[n][m];
		
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				arr[i][j]=sc.nextInt();
		
		lastAttack=new int[n][m];
		
		for(int round=1;round<=k;round++) {
			// 종료 조건 체크
			if(isFinish())
				break;
			
			// 매 라운드마다 공격 관련 여부 초기화
			isAttacked = new boolean[n][m];
			
			// 1. 공격자 선정
			int[] attacker=searchAttacker();
			arr[attacker[0]][attacker[1]]+=(n+m); // 공격력 증가
			isAttacked[attacker[0]][attacker[1]]=true; // 공격 여부 처리
			lastAttack[attacker[0]][attacker[1]]=round; // 공격 시점 저장
			
			// 2. 공격자 공격
			// 타켓 선정
			int[] target=searchTarget(attacker);
			isAttacked[target[0]][target[1]]=true; // 공격 여부 변경
			
			// 3. 공격
			if(!laser(attacker,target))
				bomb(attacker,target);
			
			// 4. 포탑 부서짐 : 공격력 0 이하는 부서짐
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(arr[i][j]<0)
						arr[i][j]=0;
				}
			}
			
			// 5. 포탑 정비 : 공격력과 무관하고, 부서지지 않은 포탑은 공격력 +1
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(arr[i][j]>0&&!isAttacked[i][j])
						arr[i][j]+=1;
				}
			}
		}
		
		// 가장 공력력이 높은 값 출력
		int max=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(arr[i][j]>max)
					max=arr[i][j];
			}
		}
		
		System.out.println(max);
	}
	
	// 종료 조건 : 포탑이 하나만 있을 경우
	static boolean isFinish() {
		int count=0;
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(arr[i][j]!=0)
					count++;
			}
		}
		
		if(count==1)
			return true;
		else 
			return false;
	}
	
	// 공격자 선정 함수
	static int[] searchAttacker() {
		int[] info=new int[2]; // 공격자 좌표 전달
		int ax=0, ay=0;
		int power=5001; // 최대가 5000
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(arr[i][j]==0)
					continue;
				
				// 공격력이 가장 낮아야 함
				if(arr[i][j]<power) {
					power=arr[i][j];
					ax=i;
					ay=j;
					continue;
				}
				else if(arr[i][j]>power)
					continue;
				
				// 값이 클수록 최근에 공격한 포탑
				if(lastAttack[i][j]>lastAttack[ax][ay]) {
					power=arr[i][j];
					ax=i;
					ay=j;
					continue;
				}
				else if(lastAttack[i][j]<lastAttack[ax][ay])
					continue;
				
				// 행+열 값이 큰 포탑
				if(i+j>ax+ay) {
					power=arr[i][j];
					ax=i;
					ay=j;
					continue;
				}
				else if(i+j<ax+ay)
					continue;
				
				// 열 값이 더 큰 포탑
				if(j>ay) {
					power=arr[i][j];
					ax=i;
					ay=j;
				}
			}
		}
		
		info[0]=ax;
		info[1]=ay;
		
		return info;
	}
	
	// 타겟 선정 함수
	static int[] searchTarget(int[] attacker) {
		int power=-1;
		int tx=0, ty=0;
		int[] info=new int[2];
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				// 공격자를 제외해야 함
				if(attacker[0]==i&&attacker[1]==j)
					continue;
				
				// 공격력이 없는 포탑 제외
				if(arr[i][j]==0)
					continue;
				
				// 공격력이 가장 높은 포탑
				if(power<arr[i][j]) {
					power=arr[i][j];
					tx=i;
					ty=j;
					continue;
				}
				else if(power>arr[i][j])
					continue;
				
				// 공격한지 오래된 포탑
				if(lastAttack[i][j]<lastAttack[tx][ty]) {
					power=arr[i][j];
					tx=i;
					ty=j;
					continue;
				}
				else if(lastAttack[i][j]>lastAttack[tx][ty])
					continue;
				
				// 행+열이 작은 포탑
				if(i+j<tx+ty) {
					power=arr[i][j];
					tx=i;
					ty=j;
					continue;
				}
				else if(i+j>tx+ty)
					continue;
				
				// 열 값이 작은 포탑
				if(j<ty)  {
					power=arr[i][j];
					tx=i;
					ty=j;
				}
			}
		}
		
		info[0]=tx;
		info[1]=ty;
		
		return info;
	}
	
	// 레이저 공격
	static boolean laser(int[] attacker, int[] target) {
		boolean[][] visited=new boolean[n][m];
		Node_포탑부수기[][] route=new Node_포탑부수기[n][m]; // 역추적 경로를 위한 배열
		
		Queue<Node_포탑부수기> q=new LinkedList<>();
		q.add(new Node_포탑부수기(attacker[0],attacker[1]));
		visited[attacker[0]][attacker[1]]=true;
		
		while(!q.isEmpty()) {
			Node_포탑부수기 now=q.poll();
			
			for(int i=0;i<4;i++) {
				int nx=(now.x+dx[i]+n)%n;
				int ny=(now.y+dy[i]+m)%m;
				
				// 방문하지 않았고, 부서서지 않은 포탄인 경우
				if(!visited[nx][ny]&&arr[nx][ny]!=0) {
					visited[nx][ny]=true;
					route[nx][ny]=new Node_포탑부수기(now.x,now.y); // 직전에 거쳐간 경로 저장
					q.add(new Node_포탑부수기(nx,ny));
				}
			}
		}
		
		// 공격대상 위치까지 못가는 경우 return false -> 포탄공격
		if(!visited[target[0]][target[1]])
			return false;
		
		// 역추적, target에서 attacker 경로로 이동
		int x=target[0], y=target[1];
		while(x!=attacker[0]||y!=attacker[1]) {
			int power=arr[attacker[0]][attacker[1]]/2;
			
			// 타겟인 경우에는 공격자의 공격력 만큼 감소
			if(x==target[0]&&y==target[1])
				power=arr[attacker[0]][attacker[1]];
			
			// 경로에 있는 포탑 공격력 감소
			arr[x][y]-=power; 
			isAttacked[x][y]=true; // 공격 여부 체크
			
			Node_포탑부수기 next=route[x][y]; // 역추적 경로 
			x=next.x;
			y=next.y;
		}
		
		return true;
	}
	
	// 포탄 공격
	static void bomb(int[] attacker, int[] target) {
		// 타겟은 공격자의 공격력 만큼 감소
		arr[target[0]][target[1]]-=arr[attacker[0]][attacker[1]];
		isAttacked[target[0]][target[1]]=true; // 공격 여부 체크
		
		int power=arr[attacker[0]][attacker[1]]/2;
		for(int i=0;i<8;i++) {
			int nx=(target[0]+ddx[i]+n)%n;
			int ny=(target[1]+ddy[i]+m)%m;
			
			// 공격자는 영향 X
			if(nx==attacker[0]&&ny==attacker[1])
				continue;
			
			arr[nx][ny]-=power;
			isAttacked[nx][ny]=true; // 공격 여부 체크
		}
	}
}

 

[고찰]

 이번 문제는 삼성 SW 역량테스트 기출문제로 여태까지 풀어봤던 삼성 문제 중 코드가 가장 긴 문제였던 것 같다. 해당 문제에서 어려운 점은 레이저 공격 부분인데 경로 역추적을 하여 해결할 수 있었다. 경로를 탐색하면서 이전에 지나왔던 좌표 값을 저장한 후, 도착 지점부터 다시 시작 지점까지 되돌아 가는 것이다. 이 부분을 제외하고는 크게 어려운 부분은 없었지만 문제를 꼼꼼히 읽지 않으면 놓칠 수 있는 조건들이 너무 많은 문제였다..