[CodeTree] 삼성 SW 역량테스트 2023 하반기 오전 1번 문제 - 왕실의 기사

문제설명

왕실의 기사들은 L×L 크기의 체스판 위에서 대결을 준비하고 있습니다. 체스판의 왼쪽 상단은 (1,1)로 시작하며, 각 칸은 빈칸, 함정, 또는 벽으로 구성되어 있습니다. 체스판 밖도 벽으로 간주합니다.

왕실의 기사들은 자신의 마력으로 상대방을 밀쳐낼 수 있습니다. 각 기사의 초기위치는 (r,c)로 주어지며, 그들은 방패를 들고 있기 때문에 (r,c)를 좌측 상단으로 하며 h(높이)×w(너비) 크기의 직사각형 형태를 띄고 있습니다. 각 기사의 체력은 k로 주어집니다.

(1) 기사 이동

왕에게 명령을 받은 기사는 상하좌우 중 하나로 한 칸 이동할 수 있습니다. 이때 만약 이동하려는 위치에 다른 기사가 있다면 그 기사도 함께 연쇄적으로 한 칸 밀려나게 됩니다. 그 옆에 또 기사가 있다면 연쇄적으로 한 칸씩 밀리게 됩니다. 하지만 만약 기사가 이동하려는 방향의 끝에 벽이 있다면 모든 기사는 이동할 수 없게 됩니다. 또, 체스판에서 사라진 기사에게 명령을 내리면 아무런 반응이 없게 됩니다.

(2) 대결 대미지

명령을 받은 기사가 다른 기사를 밀치게 되면, 밀려난 기사들은 피해를 입게 됩니다. 이때 각 기사들은 해당 기사가 이동한 곳에서 w×h 직사각형 내에 놓여 있는 함정의 수만큼만 피해를 입게 됩니다. 각 기사마다 피해를 받은 만큼 체력이 깎이게 되며, 현재 체력 이상의 대미지를 받을 경우 기사는 체스판에서 사라지게 됩니다. 단, 명령을 받은 기사는 피해를 입지 않으며, 기사들은 모두 밀린 이후에 대미지를 입게 됩니다. 밀렸더라도 밀쳐진 위치에 함정이 전혀 없다면 그 기사는 피해를 전혀 입지 않게 됨에 유의합니다.

Q 번에 걸쳐 왕의 명령이 주어졌을 때, Q 번의 대결이 모두 끝난 후 생존한 기사들이 총 받은 대미지의 합을 출력하는 프로그램을 작성해보세요.

입력 형식
첫 번째 줄에 L, N, Q가 공백을 사이에 두고 주어집니다.

다음 L 개의 줄에 걸쳐서 L×L 크기의 체스판에 대한 정보가 주어집니다.

0이라면 빈칸을 의미합니다.
1이라면 함정을 의미합니다.
2라면 벽을 의미합니다.
다음 N 개의 줄에 걸쳐서 초기 기사들의 정보가 주어집니다. 이 정보는 (r,c,h,w,k) 순으로 주어지며, 이는 기사의 처음 위치는 (r,c)를 좌측 상단 꼭지점으로 하며 세로 길이가 h, 가로 길이가 w인 직사각형 형태를 띄고 있으며 초기 체력이 k라는 것을 의미합니다. 입력은 1번 기사부터 N번 기사까지 순서대로 정보가 주어집니다.

단, 처음 주어지는 기사들의 위치는 기사들끼리 서로 겹쳐져 있지 않습니다. 또한 기사와 벽은 겹쳐서 주어지지 않습니다.

다음 Q 개의 줄에 걸쳐 왕의 명령에 대한 정보가 주어집니다. 이 정보는 (i,d) 형태로 주어지며 이는 i번 기사에게 방향 d로 한 칸 이동하라는 명령임을 뜻합니다. i는 1 이상 N 이하의 값을 갖으며, 이미 사라진 기사 번호가 주어질 수도 있음에 유의합니다. d는 0, 1, 2, 3 중에 하나이며 각각 위쪽, 오른쪽, 아래쪽, 왼쪽 방향을 의미합니다.

L: 체스판의 크기 (3≤L≤40)
N: 기사의 수 (1≤N≤30)
Q: 명령의 수 (1≤Q≤100)
k: 기사의 체력 (1≤k≤100)
출력 형식
Q 개의 명령이 진행된 이후, 생존한 기사들이 총 받은 대미지의 합을 출력합니다.

입출력 예제
예제1
입력:

4 3 3
0 0 1 0
0 0 1 0
1 1 0 1
0 0 2 0
1 2 2 1 5
2 1 2 1 1
3 2 1 2 3
1 2
2 1
3 3
출력:

3

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	static int L, N, Q;
	static Set<Integer> pick;
	static Knight[] knights;
	static int[][] knightIdx, damage, dir= {{-1,0},{0,1},{1,0},{0,-1}};
	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());
		pick = new HashSet();
		knightIdx = new int[L][L];
		damage = new int[L][L];
		knights = new Knight[N+1];
		// 체스판 정보
		for(int i=0; i<L; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<L; j++) {
				damage[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// N개의 기사
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken())-1;
			int y = Integer.parseInt(st.nextToken())-1;
			int h = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			Knight knight = new Knight(i, x, y, h, w, k);
			knights[i] = knight;
			for(int j=x; j<x+h; j++) {
				for(int l=y; l<y+w; l++) {
					knightIdx[j][l] = i;
				}
			}
		}
		// 명령
		while(Q-- > 0) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			// 기사 이동
			pick = new HashSet<>();
			if(knights[i] != null) {
				knightMove(i, d);
			}
			
			// 기사들 재정비
			setting();
		}
		int answer = 0;
		for(int i=1; i<=N; i++) {
			if(knights[i] == null) continue;
			answer += (knights[i].originK - knights[i].k);
		}
		System.out.println(answer);
	}
	private static void setting() {
		knightIdx = new int[L][L];
		for(int d=1; d<=N; d++) {
			if(knights[d] == null) continue;
			Knight knight = knights[d];
			int idx = knight.idx;
			int x = knight.x;
			int y = knight.y;
			int h = knight.h;
			int w = knight.w;
			for(int i=x; i<x+h; i++) {
				for(int j=y; j<y+w; j++) {
					knightIdx[i][j] = idx;
				}
			}
		}
	}
	private static void knightMove(int target, int d) {
		Queue<Knight> q = new ArrayDeque<>();
		q.offer(knights[target]);
		while(!q.isEmpty()) {
			Knight now = q.poll();
			int idx = now.idx;
			int x = now.x;
			int y = now.y;
			int h = now.h;
			int w = now.w;
			// 현재 기사가 한 칸 이동했을 때
			int nx = x + dir[d][0];
			int ny = y + dir[d][1];
			
			// 움직인 범위 내에 다른 기사 있는지
			for(int i=nx; i<nx+h; i++) {
				for(int j=ny; j<ny+w; j++) {
					if(i<0 || j<0 || i>=L || j>=L || damage[i][j]==2) { // 벽이 있거나 체스판 벗어나면
						return;
					}
					if(knightIdx[i][j] != 0 && knightIdx[i][j] != idx) { // 다른 기사가 있다면
						Knight next = knights[knightIdx[i][j]];
						pick.add(knightIdx[i][j]);
						q.offer(next);
					}
				}
			}
		}
		// 데미지 입은 기사들
		for(Integer idx : pick) {
			if(idx == target) continue;
			Knight knight = knights[idx];
			int x = knight.x += dir[d][0];
			int y = knight.y += dir[d][1];
			int h = knight.h;
			int w = knight.w;
			
			// damage 입기
			for(int i=x; i<x+h; i++) {
				for(int j=y; j<y+w; j++) {
					if(damage[i][j] == 1) {
						knight.k--;
					}
				}
			}
			if(knight.k <= 0) {
				knights[idx]=null;
			}
		}
		knights[target].x += dir[d][0];
		knights[target].y += dir[d][1];
	}
	static class Knight {
		int idx, x, y, h, w, k, originK;
		public Knight(int idx, int x, int y, int h, int w, int k) {
			super();
			this.idx = idx;
			this.x = x;
			this.y = y;
			this.h = h;
			this.w = w;
			this.k = k;
			this.originK = k;
		}
	}
}

[출처]

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

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