[CodeTree] 루돌프의 반란 - Java

✨ 구현 ➡︎ 연쇄적으로 이동시키기 & 이동한 좌표 갱신하고 잘 반영시키기 

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

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

---

📍고려해야할 점 

• 산타가 가까운 루돌프에게 이동할 때, 반대로 루돌프가 가까운 산타에게 이동할 때 어느 방향으로 이동할지 결정하기 위해서는 거리 공식 계산을 이용해서 비교해야 한다.
  👉 루돌프의 경우 8방향 이동 가능하고, 산타는 4방향만 이동이 가능하다. 이동 가능한 방향에 대해 전부 탐색하여 제일 가까운 거리를 찾는다. 
• 산타는 이동할 경우가 여러 개라면 상, 우, 하, 좌 방향 우선순위에 맞춰 이동한다. 👉 루돌프는 이동할 경우가 1개만 나올 것이다. 
• 산타의 경우 이동 가능하지만 현재 위치해 있는 곳이 가장 가까운 거리라면 즉, 루돌프로부터 가까워질 수 있는 방법이 없다면 이동하지 않는다. 
• 루돌프와 충돌한 산타가 상호작용으로 다른 칸에 착지하려고 할 때 이미 그 칸에 다른 산타가 존재하면 연쇄적으로 1칸씩 이동한다. 
• 루돌프와 충돌한 산타는 기절해 1번 턴을 쉰다. 기절한 산타는 이동할 수 없다. 
• 중간 중간 이동한 위치를 갱신하고 저장해야한다 ! 👉 실제로 이 부분을 빠뜨리고 작성한 곳이 몇 군데 있어서 디버깅하면서 애를 먹었다....

 

 

🕹️ 풀이 방법 

요구사항대로 차근차근 풀면 된다. 

 

1️⃣ 자료구조 선택

 

산타의 위치와 기절여부에 대한 요소들을 하나의 class로 만들었고,

산타의 생존 여부 boolean[] 와 현재 산타의 정보 Info[] 를 저장할 배열을 만들었다. 

산타와 루돌프의 위치를 반영시킬 board[][] 배열도 만들었다. 이 배열에는 산타의 번호(1~P)와 루돌프(-1)을 갱신해가면서 반영시킬 것이다. 

기절할 시에는 z=2로 설정하고 턴이 끝날 때마다 z가 1씩 감소하도록 하여 z=0이 되면 다시 이동할 수 있게 해 줄 것이다. 

이 외에 특별한 건 딱히 없다. 

 

 

2️⃣ 루돌프의 움직임 - moveR()

• 가장 가까운 산타를 찾기 위해 살아있는 모든 산타와의 거리를 계산한다.
• 가장 가까운 산타를 찾았다면 이동할 수 있는 8방향 중 찾은 산타와 가장 가깝게 이동할 수 있는 방향을 모두 계산하여 찾는다.
• 만약 이동하려는 곳에 산타가 있다면 산타와 충돌한다. 
• 루돌프가 움직여서 충돌이 일어난 경우이므로 collideWithSanta() 메서드를 호출한다.
  
  • 현재 루돌프의 방향과 위치, 해당하는 칸에 위치하는 산타의 번호를 매개변수로 넘겨준다.
  • 산타는 C만큼 점수를 획득하며 동시에 루돌프의 방향대로 C칸만큼 밀려난다. 
  • 밀려난 칸이 범위 밖이라면 산타는 탈락한다.
  • 밀려난 칸에 다른 산타가 존재하면 상호작용 interact()이 발생한다. 
    • 다른 산타는 1칸 해당 방향으로 밀려나가고 이동한 칸에 또 산타가 존재하면 연쇄적으로 1칸씩 밀려나는 것을 반복한다.

 

3️⃣ 산타의 움직임 - moveS()

 

루돌프의 움직임과 비슷하다. 

다만 다소 다른 조건들이 있어서 이 부분을 잘 고려해서 코드를 작성하면 된다. 

 

 

4️⃣ 충돌 - collideWithSanta(), collideWithR()

 

산타가 점수를 획득하고, 기절 여부에 대한 정보를 잊지 말고 작성하면 된다. 

밀려난 칸에 다른 산타가 있을 경우 상호작용 함수를 호출한다. 

 

 

5️⃣ 상호작용 - interact()

 

하나하나 swap시키는 형태로 작성했다. 

만약 이동하려는 칸에 아무도 없다면 더이상 밀려날 산타가 없으므로 break하면 된다.

주의할 점은 이동하고나서의 정보를 갱신하고 잘 반영해야 한다 !! 

 

 

 

 

👩‍💻 전체 코드 

public class final_2023_1_루돌프의반란 {
	static int N, M, P, C, D;
	static int rx, ry; // 루돌프 위치 
	static boolean[] santaDie; // 산타 생존 여부 
	static Info[] santa;
	static int[][] board;
	static int[][] newBoard;
	static int[] score;
	static int santaTargetX, santaTargetY;
	
	static int[] dx = {-1, 0, 1, 0, -1, -1, 1, 1}; // 상우하좌, 그다음 대각선
	static int[] dy = {0, 1, 0, -1, -1, 1, 1, -1};
	
	static class Info{
		int x, y, z;
		
		public Info(int x, int y, int z) {
			this.x=x;
			this.y=y;
			this.z=z; // 기절할 경우 쉬어야할 턴 표시
		}
	}
	
	static void simulate() {
		moveR();
		moveS();
	}
	
	// #1. 루돌프 움직임 
	static void moveR(){
		
		int min=Integer.MAX_VALUE;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(board[i][j]>0) {
					Info s = santa[board[i][j]];
					int len = (int) (Math.pow(s.x-rx,2) + Math.pow(s.y-ry, 2));
					if(len<=min) {
						min = len;
						santaTargetX = s.x;
						santaTargetY = s.y;
					}
				}
			}
		}
		
		min=Integer.MAX_VALUE;
		int nrx=0, nry=0, nd=0;
		
		// 가장 가까운 산타 쪽으로 이동 (8방향 중 1방향 선택)
		for(int i=0; i<8; i++) {
			int nx = rx+dx[i];
			int ny = ry+dy[i];
			if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
			int len = (int) (Math.pow(santaTargetX-nx,2) + Math.pow(santaTargetY-ny, 2));
			if(len<min) {
				min = len;
				nrx = nx;
				nry = ny;
				nd = i;
			}
		}
		// 이동하려는 곳에 산타가 있다면 산타와 충돌  --> 산타는 루돌프 방향으로 밀려남
		if(board[nrx][nry]>0) {
			collideWithSanta(nd, nrx, nry, board[nrx][nry]);
		}
		
		board[rx][ry] = 0; // 현재 루돌프 위치에 루돌프 표시 제거  
		// 루돌프 이동 완료 
		rx = nrx;
		ry = nry;
		board[rx][ry] = -1; // 이동하려는 위치에 루돌프 표시 추가
	}
	
	// #2. 산타 움직임
	static void moveS() {
		int min;
		int nsx=0, nsy=0, nd=0;
		int nx, ny;
		// 기절하지 않거나 탈락하지 않은 산타 이동 
		for(int i=1; i<=P; i++) {
			Info s = santa[i];
			nx = s.x;
			ny = s.y;
            // len = 산타 현재 위치부터 루돌프까지의 거리 
			int len = (int) (Math.pow(nx-rx, 2) + Math.pow(ny-ry, 2));
			min = len;
			
			if(s.z>0 || santaDie[i]) continue;
			for(int d=0; d<4; d++) {
				nx = s.x+dx[d];
				ny = s.y+dy[d];
				
				if(nx<0 || ny<0 || nx>=N || ny>=N || board[nx][ny]>0) continue;
				int nlen = (int) (Math.pow(rx-nx,2) + Math.pow(ry-ny, 2));
				if(nlen<min) {
					min = nlen;
					nsx = nx;
					nsy = ny;
					nd = d;
				}
			}
			if(nx==s.x && ny==s.y) continue;
			if(min==len) continue; // 움직일 수 있는 칸이 있더라도 만약 루돌프로부터 가까워질 수 있는 방법이 없다면 산타 이동 X
			board[s.x][s.y]=0; // 산타가 있었던 곳 0으로 만들기
			
			// 이동하려는 곳에 루돌프가 있다면 루돌프와 충돌 --> 산타는 반대방향으로 밀려남 
			if(board[nsx][nsy]==-1) {
				collideWithR(nd, nsx, nsy, i);
				continue;
			}
			
			// 산타 이동 완료
			s.x = nsx;
			s.y = nsy;
			board[s.x][s.y]=i; // 산타 이동한 곳에 표시
		}
		
	}
	
	// #3-1. 루돌프 -> 산타 충돌 
	static void collideWithSanta(int d, int x, int y, int n) {
		score[n]+=C; // 산타는 C만큼 점수 획득 
		santa[n].z=2; // 산타 기절 
		
		// 산타는 루돌프가 이동해온 방향으로 C칸 만큼 밀려남 
		int nsx = x+dx[d]*C;
		int nsy = y+dy[d]*C;
		
		// 만약 밀려난 위치가 게임판 밖이라면 산타는 탈락
		if(nsx<0 || nsy<0 || nsx>=N || nsy>=N) {
			santaDie[n]=true;
			return;
		}
		
		// 만약 밀려난 칸에 다른 산타가 있는 경우 상호작용 발생
		if(board[nsx][nsy]>0) interact(d, nsx, nsy, board[nsx][nsy]);
		santa[n].x = nsx;
		santa[n].y = nsy;
		board[nsx][nsy] = n;
	}
	
	// #3-2. 산타 -> 루돌프 충돌 
    static void collideWithR(int d, int x, int y, int n) {
        score[n]+=D; // 산타는 D만큼 점수 획득 
        santa[n].z=2; // 산타 기절 

        // 산타는 본인이 이동해 온 반대 방향으로 D칸 만큼 밀려남 
        if(d==0 || d==1) d+=2;
        else d-=2;

        int nsx = x+dx[d]*D;
        int nsy = y+dy[d]*D;

        // 만약 밀려난 위치가 게임판 밖이라면 산타는 탈락
        if(nsx<0 || nsy<0 || nsx>=N || nsy>=N) {
            santaDie[n]=true;
            return;
        }

        // 만약 밀려난 칸에 다른 산타가 있는 경우 상호작용 발생
        if(board[nsx][nsy]>0) {
            interact(d, nsx, nsy, board[nsx][nsy]);
        }

        santa[n].x = nsx;
        santa[n].y = nsy;
        board[nsx][nsy] = n;
    }
	
	// #4. 상호작용 : 충돌한 산타는 1칸씩 밀리게 됨 -> 연쇄적으로 1칸 이동 반복 
	static void interact(int d, int x, int y, int n) {
		
		while(true) {
			Info s = santa[n];
			int nx=s.x+dx[d];
			int ny=s.y+dy[d];
			if(nx<0 || ny<0 || nx>=N || ny>=N) {
				santaDie[n]=true;
				break;
			}
			if(board[nx][ny]>0) {
				int tmp = board[nx][ny];
				board[nx][ny]=n;
				n = tmp;
				s.x=nx;
				s.y=ny;
			}
			else if(board[nx][ny]==0) {
				board[nx][ny] = n;
				s.x = nx;
				s.y = ny;
				break;
			}
		}
	}
	
	// 살아있는 산타 점수 획득 
	static void getScore() {
		for(int i=1; i<santa.length; i++) {
			if(!santaDie[i]) score[i]++;
		}
	}
	
	// 기절한 산타 회복 
	static void recovery() {
		for(int i=1; i<santa.length; i++) {
			if(!santaDie[i] && santa[i].z>0) santa[i].z--;
		}
	}
	
	// 살아있는 산타 수 확인 
	static int checkSanta() {
		int cnt=0;
		for(int i=1; i<santa.length; i++) {
			if(!santaDie[i]) cnt++;
		}
		return cnt;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken()); // 게임판의 크기 
		M = Integer.parseInt(st.nextToken()); // 게임 턴 수 
		P = Integer.parseInt(st.nextToken()); // 산타의 수 
		C = Integer.parseInt(st.nextToken()); // 루돌프 힘 
		D = Integer.parseInt(st.nextToken()); // 산타 힘 
		board = new int[N][N];
		newBoard = new int[N][N];
		santa = new Info[P+1];
		score = new int[P+1];
		santaDie = new boolean[P+1];
		
		st = new StringTokenizer(br.readLine());
		rx = Integer.parseInt(st.nextToken())-1; // 루돌프 위치 
		ry = Integer.parseInt(st.nextToken())-1;
		board[rx][ry]=-1;
		
		for(int i=1; i<=P; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken())-1;
			int y = Integer.parseInt(st.nextToken())-1;
			santa[n] = new Info(x, y, 0);
			board[x][y]=n;
		}
		
		while(M-->0) {
			simulate();
			getScore();
			
			if(checkSanta()==0) break;
			// 한 턴이 끝날 때마다 기절한 산타 회복
			recovery();
		}
		
		for(int i=1; i<=P; i++) {
			bw.write(score[i] + " ");
		}
		bw.flush();
		bw.close();
	}
}