왕실의 기사 대결(삼성 sw역량테스트)

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

 

구현 + bfs

풀이과정

0. 모듈화된 함수를 다 호출하는 solve함수.

static void solve(int n,int d) {
		
		if(knights[n].isOut) return;
		
		// 1. 해당 방향으로 이동이 가능한지 확인하기
		if(!movable(n,d)) return;
		
		// 2. 이동시키기
		moved = new boolean[N+1];
		move(n, d);
		moved[n] = false; // 명령받은 n번 기사는 움직임에서 제외
		// 3. 데미지 계산하기 (명령을 받은 n번 기사는 데미지를 입지 않음) 
		calcDamage();
		
	}

이때 move(n,d); 함수를 호출한 뒤 move[n] 을 false로 해준이유는, 문제조건에서 움직인 체스에 대해서는 데미지를 계산하지 않는다고 명시되어 있기 때문입니다.

 

아래부터는 solve함수 내부적으로 호출하는 모듈화 된 함수 입니다.

 

1. n번 기사를 d방향으로 움직일 수 있는지 확인하는 movable 함수

static boolean movable(int n,int d) { // n번 기사를 d방향으로 이동시킬 수 있는지 확인
		Deque<int[]> q = new ArrayDeque<>();
		Knight knight = knights[n];
		
		for(int r=knight.r; r<knight.r+knight.h; r++) {
			for(int c=knight.c; c<knight.c+knight.w; c++) {
				q.offer(new int[] {r,c,n});
			}
		}
		
		while(!q.isEmpty()) {
			int[] cur = q.pollFirst();
			int cr = cur[0];
			int cc = cur[1];
			int ck = cur[2]; // 현재 탐색중인 기사
			
			int nr = cr + dr[d]; // d 방향
			int nc = cc + dc[d];
			
			if(nr<0 || nr>=L || nc<0 || nc>=L || map[nr][nc]==2) return false; // 벽을 만나면 이동하지 못함
			if(knight_map[nr][nc]==ck) continue;
			if(knight_map[nr][nc]==0) continue; 
			
			// 탐색중인 기사와 다른 기사를 만나면 큐에 해당 기사들 다 넣어주기
			if(knight_map[nr][nc]!=ck) {
				bfs(nr,nc,q);
			}
		}
		return true;
	}

 

d 방향에 벽이 있으면(움직이지 못하면) false를 리턴합니다.

d 방향이 현재 탐색하는 기사영역이라면 continue해야 합니다.

d방향이 현재 탐색중인 기사와 다른 기사라면 해당 기사들을 큐에 다 넣어줘야 합니다.

이를 위해서 bfs함수 호출하고, 매개변수로 현재 큐를 넣어줬습니다.

movable 함수 끝까지 도달했다면, 해당 기사를 움직일 수 있다는 의미이므로 true를 리턴해줍니다.

 

movable 함수에서 내부적으로 호출하는 bfs함수

static void bfs(int r,int c, Deque<int[]> q) { // 이동하려는 기사와 인접한 기사들을 큐에 넣어주는 BFS함수
		boolean[][] bfs_visited = new boolean[L][L];
		Deque<int[]> bfs_q = new ArrayDeque<>();
		
		bfs_visited[r][c] = true;
		bfs_q.offer(new int[] {r,c,knight_map[r][c]});
		
		// movable 큐 업데이트
		
		q.offer(new int[] {r,c,knight_map[r][c]});
		
		while(!bfs_q.isEmpty()) {
			int[] cur = bfs_q.pollFirst();
			int cr = cur[0];
			int cc = cur[1];
			int ck = cur[2]; // 현재 탐색중인 기사
			
			for(int d=0;d<4;d++) {
				int nr = cr + dr[d];
				int nc = cc + dc[d];
				if(nr<0 || nr>=L) continue;
				if(nc<0 || nc>=L) continue;
				if(bfs_visited[nr][nc]) continue;
				
				if(knight_map[nr][nc]==ck) {
					bfs_visited[nr][nc] = true;
					bfs_q.offer(new int[] {nr,nc,ck});
					
					// movable 큐 업데이트
					q.offer(new int[] {nr,nc,ck});
				}
			}
		}
	}

 

 

bfs를 통해 매개변수로 넘겨준 체스 영역을 찾고, 그 좌표들을 매개변수로 넘겨준 큐에 넣어주는 함수입니다.

 

 

2. 움직이는 함수 move

static void move(int n,int d) {
		Knight knight = knights[n];
		moved[n] = true;
		
		for(int i=knight.r;i<knight.r+knight.h;i++) {
			for(int j=knight.c;j<knight.c+knight.w;j++) {
				
				int nr = i + dr[d];
				int nc = j + dc[d];
				
				// nr, nc위치에 또 다른 기사가 있으면 그 기사들 이동시키기
				if(knight_map[nr][nc]!=0 && knight_map[nr][nc]!=n) {
					move(knight_map[nr][nc],d);
				}
			}
		}
		
		// 이동시키기
		for(int i=knight.r;i<knight.r+knight.h;i++) {
			for(int j=knight.c;j<knight.c+knight.w;j++) {
				knight_map[i][j] = 0;
			}
		}
		
		for(int i=knight.r;i<knight.r+knight.h;i++) {
			for(int j=knight.c;j<knight.c+knight.w;j++) {
				int nr = i + dr[d];
				int nc = j + dc[d];
				knight_map[nr][nc] = n;
			}
		}
		knight.r += dr[d];
		knight.c += dc[d];
	}

기사들은 연쇄적으로 움직이므로, 재귀를 활용했습니다. 

nr,nc위치에 또 다른 기사가 있다면 그 기사들을 이동 시킨 후에 현재 기사들을 움직이고 knight 객체의 좌표또한 업데이트 시켜줍니다.

재귀는 스택 자료구조와 일치합니다(선입후출). 따라서 제일 마지막 기사들 부터 움직이게 되므로 위와 같이 구현할 수 있었습니다.

또한 moved변수를 true로 설정해줬는데, 이는 3번에서 할 데미지 계산을 위한 변수입니다.

 

3. 데미지를 계산하는 함수 calcDamage

static void calcDamage() {
		
		for(int n=1;n<N+1;n++) {
			if(moved[n]) {
				Knight knight = knights[n];
				for(int i=knight.r;i<knight.r+knight.h;i++) {
					for(int j=knight.c;j<knight.c+knight.w;j++) {
						if(map[i][j]==1) {
							knight.k-=1;
							knight.damage+=1;
							if(knight.k==0) { // 아웃된 기사는 더 이상 데미지를 계산할 필요 없음
								knight.isOut = true;
								erase(n); // n번 기사 knight_map 배열에서 지우기
								break;
							}
						}
					}
					if(knight.isOut) { // 아웃된 기사는 더 이상 데미지를 계산할 필요 없음
						break;
					}
				}
			}
		}
	}

움직인 체스들에 대해서 체력을 감소시키고, 데미지를 증가시킵니다.

이때 만약 체력이 0이된다면 객체의 변수 isOut를 true로 시켜주고 해당 체스영역을 지우는 erase함수를 실행합니다.

또한 더 이상 데미지를 계산할 필요가 없으므로 break문으로 반복문을 탈출해줍니다.

알게된점

• 하나의 이차원 배열에 모든 값을 나타낼 필요가 없음을 알게되었습니다. 해당 문제의 경우 벽과 함정을 저장하는 이차원 배열 int[][] map, 기사들의 영역을 저장하는 2차원 배열 int[][] knight_map을 활용했습니다.
• 또한 2차원 배열에 객체를 직접 할당할 필요 없이 Knight[] knights와 같은 객체 배열에서 객체를 관리하고, 2차원 배열에는 객체들을 식별할 수 있는 식별자만 두는 방식으로 문제를 해결할 수 있음을 알게되었습니다.
• movable 함수를 구현할 때, bfs 내부에서 bfs를 호출하는 형식이었습니다. 영역별에 대해 체크를 진행할 때 bfs를 활용할 수 있음을 알게되었습니다.
• 연쇄작용의 경우 재귀(stack 자료구조)를 활용하여 구현할 수 있음을 알게되었습니다.

전체코드

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

// 영역을 이동시키는 것

class Knight{
	int r,c;
	int h,w;
	int k; // 체력
	int damage;
	boolean isOut;
	
	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;
	}

	@Override
	public String toString() {
		return "Knight [r=" + r + ", c=" + c + ", h=" + h + ", w=" + w + ", k=" + k + ", damage=" + damage + ", isOut="
				+ isOut + "]";
	}
	
}


public class Main {
	
	// 입력 값
	static int L,N,Q;
	// 체스판을 나타내는 배열
	static int[][] map;
	// 기사들의 위치를 나타내는 배열
	static int[][] knight_map;
	// 기사들을 관리하는 배열
	static Knight[] knights;
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	// 데미지를 계산하기 위해 이동한 기사들을 표시하기 위한 배열
	static boolean[] moved;
	
	static void bfs(int r,int c, Deque<int[]> q) { // 이동하려는 기사와 인접한 기사들을 큐에 넣어주는 BFS함수
		boolean[][] bfs_visited = new boolean[L][L];
		Deque<int[]> bfs_q = new ArrayDeque<>();
		
		bfs_visited[r][c] = true;
		bfs_q.offer(new int[] {r,c,knight_map[r][c]});
		
		// movable 큐 업데이트
		
		q.offer(new int[] {r,c,knight_map[r][c]});
		
		while(!bfs_q.isEmpty()) {
			int[] cur = bfs_q.pollFirst();
			int cr = cur[0];
			int cc = cur[1];
			int ck = cur[2]; // 현재 탐색중인 기사
			
			for(int d=0;d<4;d++) {
				int nr = cr + dr[d];
				int nc = cc + dc[d];
				if(nr<0 || nr>=L) continue;
				if(nc<0 || nc>=L) continue;
				if(bfs_visited[nr][nc]) continue;
				
				if(knight_map[nr][nc]==ck) {
					bfs_visited[nr][nc] = true;
					bfs_q.offer(new int[] {nr,nc,ck});
					
					// movable 큐 업데이트
					q.offer(new int[] {nr,nc,ck});
				}
			}
		}
	}
	
	static boolean movable(int n,int d) { // n번 기사를 d방향으로 이동시킬 수 있는지 확인
		Deque<int[]> q = new ArrayDeque<>();
		Knight knight = knights[n];
		
		for(int r=knight.r; r<knight.r+knight.h; r++) {
			for(int c=knight.c; c<knight.c+knight.w; c++) {
				q.offer(new int[] {r,c,n});
			}
		}
		
		while(!q.isEmpty()) {
			int[] cur = q.pollFirst();
			int cr = cur[0];
			int cc = cur[1];
			int ck = cur[2]; // 현재 탐색중인 기사
			
			int nr = cr + dr[d]; // d 방향
			int nc = cc + dc[d];
			
			if(nr<0 || nr>=L || nc<0 || nc>=L || map[nr][nc]==2) return false; // 벽을 만나면 이동하지 못함
			if(knight_map[nr][nc]==ck) continue;
			if(knight_map[nr][nc]==0) continue; 
			
			// 탐색중인 기사와 다른 기사를 만나면 큐에 해당 기사들 다 넣어주기
			if(knight_map[nr][nc]!=ck) {
				bfs(nr,nc,q);
			}
		}
		return true;
	}
	
	static void move(int n,int d) {
		Knight knight = knights[n];
		moved[n] = true;
		
		for(int i=knight.r;i<knight.r+knight.h;i++) {
			for(int j=knight.c;j<knight.c+knight.w;j++) {
				
				int nr = i + dr[d];
				int nc = j + dc[d];
				
				// nr, nc위치에 또 다른 기사가 있으면 그 기사들 이동시키기
				if(knight_map[nr][nc]!=0 && knight_map[nr][nc]!=n) {
					move(knight_map[nr][nc],d);
				}
			}
		}
		
		// 이동시키기
		for(int i=knight.r;i<knight.r+knight.h;i++) {
			for(int j=knight.c;j<knight.c+knight.w;j++) {
				knight_map[i][j] = 0;
			}
		}
		
		for(int i=knight.r;i<knight.r+knight.h;i++) {
			for(int j=knight.c;j<knight.c+knight.w;j++) {
				int nr = i + dr[d];
				int nc = j + dc[d];
				knight_map[nr][nc] = n;
			}
		}
		knight.r += dr[d];
		knight.c += dc[d];
	}
	
	static void erase(int n) {
		Knight knight = knights[n];
		for(int i=knight.r;i<knight.r+knight.h;i++) {
			for(int j=knight.c;j<knight.c+knight.w;j++) {
				knight_map[i][j] = 0;
			}
		}
	}
	
	static void calcDamage() {
		
		for(int n=1;n<N+1;n++) {
			if(moved[n]) {
				Knight knight = knights[n];
				for(int i=knight.r;i<knight.r+knight.h;i++) {
					for(int j=knight.c;j<knight.c+knight.w;j++) {
						if(map[i][j]==1) {
							knight.k-=1;
							knight.damage+=1;
							if(knight.k==0) { // 아웃된 기사는 더 이상 데미지를 계산할 필요 없음
								knight.isOut = true;
								erase(n); // n번 기사 knight_map 배열에서 지우기
								break;
							}
						}
					}
					if(knight.isOut) { // 아웃된 기사는 더 이상 데미지를 계산할 필요 없음
						break;
					}
				}
			}
		}
	}
	
	static void solve(int n,int d) {
		
		if(knights[n].isOut) return;
		
		// 1. 해당 방향으로 이동이 가능한지 확인하기
		if(!movable(n,d)) return;
		
		// 2. 이동시키기
		moved = new boolean[N+1];
		move(n, d);
		moved[n] = false; // 명령받은 n번 기사는 움직임에서 제외
		// 3. 데미지 계산하기 (명령을 받은 n번 기사는 데미지를 입지 않음) 
		calcDamage();
		
	}
	
	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 = new int[L][L];
        knight_map = 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++) {
        		map[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        
        for(int i=1;i<N+1;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);
        	for(int a=r;a<r+h;a++) {
        		for(int b=c;b<c+w;b++) {
        			knight_map[a][b] = i;
        		}
        	}
        }

        for(int q=0;q<Q;q++) {
        	st = new StringTokenizer(br.readLine());
        	int i = Integer.parseInt(st.nextToken());
        	int d = Integer.parseInt(st.nextToken());
        	// i번 기사를 d방향으로 이동시키기
        	solve(i,d);
        }
        
        int answer = 0;
        for(int n=1;n<=N;n++) {
        	if(!knights[n].isOut) {
        		answer += knights[n].damage;
        	}
        }
        
        System.out.println(answer);
        
    }
	
	static void print(int[][] arr) {
		for(int i=0;i<arr.length;i++) {
			for(int j=0;j<arr[i].length;j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
        }
		System.out.println("-----------------");
	}
}