왕실의 기사 대결[G3]

문제

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

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

 

 

풀이

사실 기존 방식과 조금 다른 방식을 사용했다.

copy 메서드를 통해 연쇄된 행동이 잘못되었을 경우, 백업된 값으로 다시 복구하는 기능이다.

 

또한, 문제의 가장 핵심은 '한 번에, 어딘가에 이동을 저장해놨다가', 모든 조건이 만족되었을 경우에만 일괄적으로 옮기는 것이다. 개념 자체는 백트래킹과 유사했다.

 

탈락한 기사를 제거하는 것을 잊지 말 것. 테스트케이스 38번이 걸린다면, 이것의 문제일 가능성이 높다.

 

이것을 위해 tempQ의 List를 통해 움직이는 위치를 임시 보관하였고, 각 Knight 객체에 이러한 Pos(위치) 객체들을 담을 수 있는 List 구조를 만들었다.

 

코드

 

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

public class Main {
	static int L, N, Q;
	static final int DR[] = {-1, 0, 1, 0};
	static final int DC[] = {0, 1, 0, -1};
	static boolean isFail = false; //Trigger
	static Knight[] knights;
	static List<Queue<Pos>> tempQList = new ArrayList<>(); //각 연쇄 밀림에 대비, 기사별 좌표 Pos 저장용
	static Set<Integer> chained = new HashSet<>();		   //연쇄 밀림 확인용
	static List<int[]> quests = new ArrayList<>();
	static int[][] map, knightFrame, backupknightFrame;

	public static void main(String[] args) throws Exception {
		int res = 0;
		input(); //입력
		
		for(int i = 0; i < Q; i++) {
			doQuest(quests.get(i)[0] - 1, quests.get(i)[1]); //퀘스트
		}
		for(int i = 0; i < N; i++) {
			if(knights[i].damage < knights[i].k) res += knights[i].damage;
		}
		System.out.println(res);
	}
	
	
	public static void doQuest(int n, int d) {
		if(knights[n].damage >= knights[n].k) return; //사망시 스킵
		isFail = false; //초기화
		for(int i = 0; i < N; i++) tempQList.get(i).clear(); //각 기사별 tempQ 초기화
		chained.clear();//밀림 확인용 지표 초기화
		
		//기사 이동
		Knight now = knights[n];
		for(int k = 0; k < now.frame.size(); k++) {
			Pos pos = now.frame.get(k);
			int nr = pos.r + DR[d];
			int nc = pos.c + DC[d]; //한 칸 이동

			//벽이나 맵 밖, 혹은 연쇄 밀림 실패 시 UNDO 후 그대로 종료
			if(cantGo(nr, nc) || map[nr][nc] == 2 || isFail) {
				copy(false);
				return; 
			}
			
			if(knightFrame[nr][nc] != now.num && knightFrame[nr][nc] != 0) {
				chaining(d, nr, nc);
			}
			
			tempQList.get(n).add(new Pos(nr, nc)); //변경 위치 저장하기
		}
		
		////최종 저장
		if(isFail) {
			copy(false); //기존 상태로 복구 후 스킵
			return;
		} else { //성공했을 경우 현재 상태 저장
			for(int i = 0; i < N; i++) {
				move(i, tempQList.get(i), n); //기사별 전체 이동
				knights[i].frame.clear(); //기사별 현재 위치 저장 리스트 초기화
			}

			for(int i = 0; i < L; i++) { //맵 순회
				for(int j = 0; j < L; j++) {
					int num = knightFrame[i][j]; //필드에 있는 숫자 확인
					if(num == 0) continue;
					knights[num - 1].frame.add(new Pos(i, j)); //각 기사 별 위치 Pos로 저장
				}
			}

			copy(true); //최종 저장
		}
		
	}
	
	public static void chaining(int d, int lr, int lc) {
		if(isFail) return; //이미 실패했으니 스킵
		
		int num = knightFrame[lr][lc]; //부딪힌 자리에 있는 넘버링
		
		if(chained.contains(num)) return; //최초 한번만 적용
		else chained.add(num);
		
		Knight now = knights[num - 1];
		tempQList.get(num - 1).clear();
		
		for(int i = 0; i < now.frame.size(); i++) { //현재 위치 밀림 수행
			Pos pos = now.frame.get(i);
			int r = pos.r;
			int c = pos.c;
			int nr = pos.r + DR[d];
			int nc = pos.c + DC[d]; //한 칸 이동
		
			//벽이나 맵 밖, 혹은 연쇄 밀림 실패 시 실패 처리 후 그대로 종료
			if(cantGo(nr, nc) || map[nr][nc] == 2 || isFail) {
				isFail = true;
				return; 
			}
			
			if(knightFrame[nr][nc] != now.num && knightFrame[nr][nc] != 0) {
				chaining(d, nr, nc);
			}
			
			tempQList.get(num - 1).add(new Pos(nr, nc)); //변경 위치 저장하기
		}
	}
	
	public static void input() throws Exception {
		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 = new int[L][L];				//경기장
		knightFrame = new int[L][L];		//기사 점유 공간
		backupknightFrame = new int[L][L];	//백업
		
		//1. 맵
		for(int i = 0; i < L; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < L; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//2. 기사
		knights = new Knight[N]; //기사 배열
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()) - 1; //좌표
			int c = Integer.parseInt(st.nextToken()) - 1; 
			int h = Integer.parseInt(st.nextToken());	  //방패
			int w = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());	  //체력
			knights[i] = new Knight(r, c, h, w, k);
		}
		
		//3. 퀘스트
		for(int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine());
			quests.add(new int[] { 
					Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken())
			});
		}
		
		//4. frameSetting
		for(int i = 0; i < N; i++) {
			Knight now = knights[i]; //현재 기사
			now.num = i + 1;

			int maxR = now.r + now.h;
			int maxC = now.c + now.w;
			for(int r = now.r; r < maxR; r++) {
				for(int c = now.c; c < maxC; c++) {
					knightFrame[r][c] = i + 1;
					now.frame.add(new Pos(r, c));
				}
			}
		}
		copy(true);
		
		
		//5. tempQ
		for(int i = 0; i < N; i++) tempQList.add(new ArrayDeque<Pos>()); //각 기사별 별도의 tempQ를 가지고 있음.
	}
	
	public static void copy(boolean isBackup) {
		for(int i = 0; i < L; i++) {
			for(int j = 0; j < L; j++) {
				if(isBackup) backupknightFrame[i][j] = knightFrame[i][j]; //백업
				else knightFrame[i][j] = backupknightFrame[i][j]; 		  //undo
			}
		}
	}
	
	public static void removeNum(int n) {
		for(int i = 0; i < L; i++) {
			for(int j = 0; j < L; j++) {
				if(knightFrame[i][j] == n) knightFrame[i][j] = 0;
			}
		}
	}
	
	//기존 위치 전부 지우고, Queue에 저장한 위치 세이브, 데미지 계산
	public static void move(int idx, Queue<Pos> tempQ, int first) {
		if(tempQ.size() == 0) return; //이동이 있을 시에만 처리
		removeNum(idx + 1); 
		int damage = 0;
		while(!tempQ.isEmpty()) {
			Pos now = tempQ.poll();
			knightFrame[now.r][now.c] = idx + 1; //넘버링
			if(idx != first) { //명령 받은 기사 아닐 경우 데미지 체크
				if(map[now.r][now.c] == 1) damage++;
			}
		}
		knights[idx].damage += damage;
		//탈락 시 필드에서 제거
		if(knights[idx].damage >= knights[idx].k) removeNum(idx + 1);
	}
	
	
	public static boolean cantGo(int r, int c) {
		if(r < 0 || c < 0 || r >= L || c >= L) return true;
		return false;
	}
}


class Knight {
	int num, damage;
	int r, c, h, w, k;
	List<Pos> frame = new ArrayList<>();
	
	public Knight(int r, int c, int h, int w, int k) {
		this.r = r;
		this.c = c;
		this.h = h;
		this.w = w;
		this.k = k;
	}
}

class Pos {
	int r, c, value;
	public Pos(int r, int c) {
		this.r = r;
		this.c = c;
	}
}