문제

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

---

입력

첫 번째 줄에 L, N, Q가 공백을 사이에 두고 주어집니다.
다음 L 개의 줄에 걸쳐서 L×L 크기의 체스판에 대한 정보가 주어집니다.
다음 N 개의 줄에 걸쳐서 초기 기사들의 정보가 주어집니다.
다음 Q 개의 줄에 걸쳐 왕의 명령에 대한 정보가 주어집니다.

---

출력

Q 개의 명령이 진행된 이후, 생존한 기사들이 총 받은 대미지의 합을 출력합니다.

---

풀이

제한조건

• L: 체스판의 크기 (3≤L≤40)
• N: 기사의 수 (1≤N≤30)
• Q: 명령의 수 (1≤Q≤100)
• k: 기사의 체력 (1≤k≤100)

접근방법

시뮬레이션

삼성 A형 스타일의 문제로, 단순 시뮬레이션이다.
복잡해보여도 요구하는 기능을 하나씩 만들어가면 완성할 수 있다. 포기하지 말자.

완성해야 하는 기능은 크게 2가지이다

1. 기사 이동
2. 대결 대미지

0. 입력 처리
기사를 표현할 수 있는 클래스(구조체)를 하나 선언해서 받아주자.
생존한 기사들이 총 받은 대미지의 합이 출력이므로, 현재까지 받은 대미지를 기록할 수 있는 별도의 변수를 생성해두자.

또한 체스판의 정보를 담을 변수와, 기사들의 정보를 기록할 총 2개의 이차원배열을 선언해두자.

1. 기사 이동
기사의 이동을 하기 위해서 조금 더 작은 Task로 나누어 생각해보자.
기사의 이동은 또다른 기사의 움직임을 유발할 수 있다.
A기사가 이동하기 위해서는 아래와 같은 조건들이 붙는다.

- A기사가 이동하려는 방향으로 인접한 기사가 존재하는지 확인
- 인접한 기사가 있다면(B) 해당 기사도 이동할 수 있는지 확인.
- 반복...

위 과정을 보면, 전형적인 재귀의 모습을 띄고 있다.
따라서 재귀를 통해 관련된 기사가 이동할 수 있는지 확인하고 이동하는 방식을 사용하면 되겠다.

// 해당 기사는 죽었다. 이동할 수 없음.
if (knights[selected].damage >= knights[selected].k)
	return;

// 해당 기사는 더 이상 움직일 수 없다.
if (!canMove(selected, dir))
	return;

// 이동가능한 경우, 연쇄적으로 이동시키자!
move(selected, dir, true);

이동 여부를 확인하는 함수와 이동하는 함수는 구성이 비슷할 것이다.
여기서 명령을 받은 기사는 이동 시 함정에 의한 피해를 받지 않는다.
따라서 move함수에 flag 변수를 하나 추가하여, 명령에 의한 이동은 대미지 계산에서 제외하였다.

2. 대결 대미지
1에서 우리는 기사의 모든 이동을 처리했다.
이동이 발생한 기사에 대하여, 자신이 속해있는 지역에 있는 trap의 수많큼 대미지를 누적해주자.
만약 받은 대미지가 초기 체력을 넘어선다면, 기사를 기록해둔 이차원 배열에서 해당 기사의 영역을 지워주면 된다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static class Knight {
		int r;
		int c;
		int h;
		int w;
		int k;
		int damage;

		Knight() {

		}

		Knight(String[] str) {
			r = stoi(str[0]) - 1;
			c = stoi(str[1]) - 1;
			w = stoi(str[2]);
			h = stoi(str[3]);
			k = stoi(str[4]);
		}
	}

	static Knight[] knights;
	static String[] inputs;
	static int L, N, Q;
	static int[][] map, knightMap;

	final static int BLANK = 0;
	final static int TRAP = 1;
	final static int WALL = 2;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		inputs = in.readLine().split(" ");
		L = Integer.parseInt(inputs[0]);
		N = Integer.parseInt(inputs[1]);
		Q = Integer.parseInt(inputs[2]);

		map = new int[L][L];
		knightMap = new int[L][L];
		for (int i = 0; i < L; ++i) {
			inputs = in.readLine().split(" ");
			for (int j = 0; j < L; ++j) {
				map[i][j] = stoi(inputs[j]);
			}
		}
		knights = new Knight[N + 1];
		knights[0] = new Knight();
		for (int i = 1; i <= N; ++i) {
			knights[i] = new Knight(in.readLine().split(" "));
			for (int x = 0; x < knights[i].w; ++x) {
				for (int y = 0; y < knights[i].h; ++y) {
					knightMap[x + knights[i].r][y + knights[i].c] = i;
				}
			}
		}

		for (int i = 0; i < Q; ++i) {
			inputs = in.readLine().split(" ");
			int selected = stoi(inputs[0]);
			int dir = stoi(inputs[1]);
			simulation(selected, dir);
		}

		int sum = 0;
		for (Knight iter : knights)
			if (iter.k > iter.damage)
				sum += iter.damage;

		System.out.println(sum);
	}

	// select 번호의 기사가 dir 방향으로 이동한다.
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};

	private static void simulation(int selected, int dir) {
		// 해당 기사는 죽었음.
		if (knights[selected].damage >= knights[selected].k)
			return;

		if (!canMove(selected, dir))
			return;

		move(selected, dir, true);

	}

	private static void move(int selected, int dir, boolean isHero) {
		boolean flag = false;
		int baseX = knights[selected].r;
		int baseY = knights[selected].c;
		for (int i = 0; i < knights[selected].w; ++i) {
			for (int j = 0; j < knights[selected].h; ++j) {
				int x = knights[selected].r + i;
				int y = knights[selected].c + j;
				int nextX = x + dx[dir];
				int nextY = y + dy[dir];

				// 범위 밖은 이동 불가
				if (!isInRange(nextX, nextY))
					return;

				// 다음이 벽이다. 이동불가
				if (map[nextX][nextY] == WALL)
					return;

				int nearByPlayer = knightMap[nextX][nextY];

				// 이동한 칸에 다른 기사가 있는 경우
				if (nearByPlayer > 0 && nearByPlayer != selected) {
					move(nearByPlayer, dir, false);
				}

				if (map[nextX][nextY] == TRAP && !isHero)
					knights[selected].damage++;

				// 현재칸 비우기 및 최초 1회 기준점 옮기기
				knightMap[x][y] = 0;
				if (!flag) {
					flag = true;
					baseX = baseX + dx[dir];
					baseY = baseY + dy[dir];
				}
			}
		}
		knights[selected].r = baseX;
		knights[selected].c = baseY;

		for (int i = 0; i < knights[selected].w; ++i) {
			for (int j = 0; j < knights[selected].h; ++j) {
				int x = knights[selected].r + i;
				int y = knights[selected].c + j;
				if (knights[selected].k > knights[selected].damage)
					knightMap[x][y] = selected;
				else
					knightMap[x][y] = 0;
			}
		}
	}

	public static boolean canMove(int selected, int dir) {
		boolean flag = true;
		for (int i = 0; i < knights[selected].w; ++i) {
			for (int j = 0; j < knights[selected].h; ++j) {
				int nextX = knights[selected].r + i + dx[dir];
				int nextY = knights[selected].c + j + dy[dir];

				// 범위 밖은 이동 불가
				if (!isInRange(nextX, nextY))
					return false;

				// 다음이 벽이다. 이동불가
				if (map[nextX][nextY] == WALL)
					return false;

				int nearByPlayer = knightMap[nextX][nextY];

				// 이동한 칸에 다른 기사가 있는 경우
				if (nearByPlayer > 0 && nearByPlayer != selected) {
					// 다음 칸의 플레이어가 이동 불가능이다.
					if (!canMove(nearByPlayer, dir))
						return false;
				}
			}
		}
		return flag;
	}

	public static boolean isInRange(int x, int y) {
		if (0 <= x && x < L && 0 <= y && y < L)
			return true;
		return false;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}