[코드트리] 왕실의 기사 대결 - JAVA

📖문제

https://www.codetree.ai/training-field/frequent-problems/problems/royal-knight-duel/description?page=1&pageSize=20

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

 

 

🔧 풀이법

1. Map 구조체를 만들어서 트랩/벽, 기사 정보를 저장하였다

2. check 함수를 재귀적으로 구현하여 이동할 수 있는지 판별한다

3. push 함수를 재귀적으로 구현하여 이동한다. 이동하면서 damage를 계산한다

4. checkDead 함수를 통해 기사가 죽었는지 확인한다.

 

 

✏️ 소감

재귀 구현 연습을 해야겠다.... 스택오버플로우 떴음ㅜㅜㅜ

 

 

🖥️ 코드

package codetree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Codetree_왕실의기사대결 {
	static int L, N, Q;
	static Map[][] map;
	static boolean[] isDead;
	static int[] dx = {-1, 0, 1, 0};	// 상, 우, 하, 좌
	static int[] dy = {0, 1, 0, -1};
	static Knight[] knight;
	static boolean flag;
	
	static final int TRAP = 1;
	static final int WALL = 2;
	
	static class Map {
		int room;
		int knight;
		
		public Map(int room, int knight) {
			super();
			this.room = room;
			this.knight = knight;
		}
		
		@Override
		public String toString() {
			return "Map [room=" + room + ", knight=" + knight + "]";
		}
	}
	
	static class Knight {
		int x, y;
		int h, w;
		int k;
		int damage;
		
		public Knight(int x, int y, int h, int w, int k) {
			super();
			this.x = x;
			this.y = y;
			this.h = h;
			this.w = w;
			this.k = k;
			this.damage = 0;
		}

		@Override
		public String toString() {
			return "Knight [x=" + x + ", y=" + y + ", h=" + h + ", w=" + w + ", k=" + k + ", damage="
					+ damage + "]";
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		L = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		
		// map에 기사 정보와 함정/벽 정보를 동시에 저장
		map = new Map[L+1][L+1];
		knight = new Knight[N+1];
		isDead = new boolean[N+1];	// 기사가 죽었는지 판별
		
		for(int i=1; i<=L; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=L; j++) {
				map[i][j] = new Map(Integer.parseInt(st.nextToken()), 0);
			}
		}
		
		for(int num=1; num<=N; num++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			
			knight[num] = new Knight(r, c, h, w, k);
			
			// map에 기사가 차지하는 공간 정보 저장
			for(int i=r, xEnd=r+h; i<xEnd; i++) {
				for(int j=c, yEnd=c+w; j<yEnd; j++) {
					map[i][j].knight = num;
				}
			}
		}
		
		
		for(int turn=0; turn<Q; turn++) {
			st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			// 기사 이동
			moveKnight(idx, d);
			// 죽었는지 확인
			checkDead();
		}
		
		// 데미지 총합 계산
		int sum = 0;
		for(int i=1; i<=N; i++) {
			if(isDead[i]) continue;
			sum += knight[i].damage;
		}
		System.out.println(sum);
	}
	
	public static void moveKnight(int idx, int dir) {
		if(isDead[idx]) return;		// 명령 받은 기사가 죽었으면 움직일 수 없음
		
		flag = true;	
		check(idx, dir);	// 움직일 수 있는지 확인
		
		if(!flag) return; // false면 움직일 수 없음
		
		// 이동
		push(idx, dir, idx);
	}
	
	public static void push(int idx, int dir, int turn) {
		Knight cur = knight[idx];
		// 현재 위치에 있는 기사 정보 초기화
		for(int i=cur.x, xEnd = cur.x+cur.h; i<xEnd; i++) {
			for(int j=cur.y, yEnd = cur.y+cur.w; j<yEnd; j++) {				
				map[i][j].knight = 0;
			}
		}
		
		// 기준점 이동
		cur.x += dx[dir];
		cur.y += dy[dir];
		
		// 민 기사가 아닐 경우에만 데미지 계산
		if(idx != turn) {
			damage(idx);
		}
		
		// 이동하기
		for(int i=cur.x, xEnd = cur.x+cur.h; i<xEnd; i++) {
			for(int j=cur.y, yEnd = cur.y+cur.w; j<yEnd; j++) {	
				// 이동하려는 곳에 기사가 있으면 재귀 돌리기
				if(map[i][j].knight != 0) {
					push(map[i][j].knight, dir, turn);
				}
				// 이동
				map[i][j].knight = idx;
			}
		}
		
	}
	
	public static void check(int idx, int dir) {
		if(!flag) return;
		
		Knight cur = knight[idx];
		int nx = cur.x + dx[dir];
		int ny = cur.y + dy[dir];
		
		// map 범위 벗어나면 false
		if(!isRange(nx, ny)) {
			flag = false;
			return;
		}
		
		// 이동하려는 곳 확인하기
		for(int i=nx, xEnd = nx+cur.h; i<xEnd; i++) {
			for(int j=ny, yEnd = ny+cur.w; j<yEnd; j++) {
				// 이동할 때 범위를 벗어나거나 벽이 있으면 false
				if(!isRange(i, j) || map[i][j].room == WALL) {
					flag = false;
					return;
				}
				
				// map에 다른 기사가 있다면 재귀 돌리기
				if(map[i][j].knight != idx && map[i][j].knight != 0) {
					check(map[i][j].knight, dir);
				}
			}
		}
		
	}
	
	// damage 계산하기
	public static void damage(int idx) {
		Knight cur = knight[idx];
		int cnt = 0;
		for(int i=cur.x, xEnd=cur.x+cur.h; i<xEnd; i++) {
			for(int j=cur.y, yEnd=cur.y+cur.w; j<yEnd; j++) {
				if(map[i][j].room == TRAP) cnt++;
			}
		}
		cur.damage += cnt;
	}
	
	// 죽었는지 판별하기
	public static void checkDead() {
		Knight cur;
		for(int k=1; k<=N; k++) {
			cur = knight[k];
			if(cur.k <= cur.damage) {
				isDead[k] = true;
				
				// map에서 죽은 기사 정보 없애기
				for(int i=cur.x, xEnd = cur.x+cur.h; i<xEnd; i++) {
					for(int j=cur.y, yEnd=cur.y+cur.w; j<yEnd; j++) {
						map[i][j].knight = 0;
					}
				}
			}
		}
	}

	public static boolean isRange(int x, int y) {
		return x >= 1 && x <= L && y >= 1 && y <= L;
	}
}