루돌프의 반란(삼성 sw역량테스트)

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

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

풀이과정

함수별로 모듈화를 잘 시켜야했으며, 구현과정이 복잡하다 보니 처음 시작할 때 자료구조를 잘 정해서 사용해야 했습니다.

 

사용한 클래스와 변수

전체적인 산타와 루돌프의 위치는 2차원 배열(int[][] map)에 정수형으로 저장하고, 세부정보를 저장하는 변수를 만들어서 2차원 배열(int[][] map)과 연결하는 방식으로 자료구조를 사용해야 했습니다.

• Santa 클래스
  • (r, c)좌표
  • 루돌프와의 거리
  • 점수
  • 기절스택
  • 라인 아웃여부
• static int N,M,P,C,D;
• static int[][] map; // N*N, 산타들의 번호, 루돌프 표시(-1)
  • 산타와 루돌프를 N*N 배열에 정수로 표시해야 합니다.
  • 그 이유는, 산타와 루돌프 사이의 거리와 이동 방향 결정, 충돌에 따른 연쇄작용(?)을 구현해야 하기 때문입니다.
  • -1 : 루돌프
  • 1,2,3 ... P : 산타
• static Santa[] santas; // 1번 산타, 2번 산타의 정보를 저장
  • 2차원 배열 map에 산타들의 번호를 저장하고, 그 번호에 해당하는 산타 객체들을 santas 배열에 저장합니다.
  • 산타들의 기절스택과, 점수, 라인 아웃여부, 루돌프와의 거리를 저장하고 활용해야 하기 때문입니다.

• static int[] rudolf; // 루돌프의 좌표
  • 루돌프의 좌표를 기억하고 있어야, 산타와의 거리를 계산하기 편리하기 때문에 루돌프의 좌표를 1차원 배열에 저장했습니다.
• static int[] dr = {-1,0,1,0};
• static int[] dc = {0,1,0,-1};
  • 산타의 이동방향을 저장하기 위한 방향벡터 입니다.
• static int live_santa_cnt;
  
  • 현재 남아있는 산타의 갯수를 저장하는 변수입니다.
• PriorityQueue
  • 루돌프와 산타의 이동방향을 결정할 때 우선순위큐를 활용해서 구현했습니다.

 

함수

루돌프를 움직이는 함수(move_rudolf)

static void move_rudolf() {
		// 1. 가장 가까운 산타를 찾는 함수(find_nearest_santa)를 호출합니다.
		Santa finded_santa = find_nearest_santa();
        
        	// 2. 찾아진 산타 객체의 (r,c)값을 기준으로 루돌프의 방향을 설정합니다.
		int dc = 0;
		if(rudolf[1]>finded_santa.c) {
			dc = -1;
		}else if(rudolf[1]<finded_santa.c) {
			dc = 1;
		}
		int dr = 0;
		if(rudolf[0]>finded_santa.r) {
			dr = -1;
		}else if(rudolf[0]<finded_santa.r) {
			dr = 1;
		}
		
        	// 3. map배열에 원래 루돌프의 위치를 0으로 표시해줍니다.
		map[rudolf[0]][rudolf[1]]=0;
		
		int nr = rudolf[0] + dr;
		int nc = rudolf[1] + dc;
        	// 4. 새로 이동할 방향에 산타가 있으면 충돌을 구현해줍니다. (여기서 collision 충돌함수를 만들어서 사용해야 합니다.)
		if(map[nr][nc]!=0) { 
			int santa_num = map[nr][nc]; // 충돌이 발생하는 산타의 번호
			santas[santa_num].score += C;
			santas[santa_num].stack = 2;
			
            		// 여기서 collision 충돌함수를 호출합니다
			collision(santa_num,dr,dc,C); // santa_num의 산타를 dr,dc 방향으로 C칸 만큼 이동 
		}
        	// 5. map배열의 이동한 위치에 루돌프를 표시해주고, 루돌프의 좌표를 저장하는 rudolf 배열 값 또한 갱신해줍니다.
		map[nr][nc]=-1; // 루돌프 이동
		rudolf[0] = nr; // 루돌프 좌표 갱신
		rudolf[1] = nc;
	}

1. 가장 가까운 산타를 찾는 함수(find_nearest_santa)를 호출합니다.

static Santa find_nearest_santa() {
		PriorityQueue<Santa> pq = new PriorityQueue<>();
		
		for(int p=1;p<=P;p++) {// 산타들의 루돌프 까지의 거리 업데이트
			if(santas[p].out) continue;
			santas[p].updateDistance(rudolf[0],rudolf[1]); 
			pq.offer(santas[p]);
		}
		
		return pq.poll();
	}

우선순위 큐를 활용하여 가장 가까운 산타를 찾았습니다.

 

2. 찾아진 산타 객체의 (r,c)값을 기준으로 루돌프의 방향을 설정합니다.

이때 루돌프는 8방향으로 이동할 수 있기때문에 직접 거리를 계산할 필요 없이, 좌표값을 기준으로 방향을 정할 수 있었습니다.

3. map배열에 원래 루돌프의 위치를 0으로 표시해줍니다.

4. 새로 이동할 방향에 산타가 있으면 충돌을 구현해줍니다. (여기서 collision 충돌함수를 호출합니다.)

 

collision함수

static void collision(int santa_num, int dr,int dc, int n) { 
		// 1. santa_num에 해당하는 산타 객체의 r,c 값을 이동 후의 값으로 갱신해주며, map또한 0으로 표시해줍니다.
		int r = santas[santa_num].r;
		int c = santas[santa_num].c;
		map[r][c] = 0; // 원래위치 0으로 표시
		
		int nr = r + dr*n;
		int nc = c + dc*n;
		
		santas[santa_num].r = nr;
		santas[santa_num].c = nc;
		
        	// 2. 이때 만약 map을 벗어나는 좌표라면 santa 객체의 out값을 true로 설정해줍니다.
		if(nr<0 || nr>=N || nc<0 || nc>=N) {
			santas[santa_num].out = true;
            		// 3. 살아있는 산타의 갯수 또한 -1 시켜줍니다. 그리고 더 이상 함수를 탐색할 필요 없이 종료시키면 됩니다.
			live_santa_cnt -= 1;
			return;
		}
		
        	// 4. 산타 객체가 이동할 위치에 또 다른 산타가 위치해있다면, 재귀적으로 collision함수를 다시 호출해줘서 상호작용을 구현합니다.
		if(map[nr][nc]!=0) { // 또 다른 산타가 해당 위치에 있으면 dfs
			collision(map[nr][nc],dr,dc,1);
		}
        	// 5. map배열에 이동한 santa의 번호를 갱신해줍니다.
		map[nr][nc] = santa_num; //이동한 위치에 산타번호 표시
	}

5. map배열의 이동한 위치에 루돌프를 표시해주고, 루돌프의 좌표를 저장하는 rudolf 배열 값 또한 갱신해줍니다.

 

산타를 움직이는 함수(move_santa)

static void move_santa() {
		
		for(int p=1;p<=P;p++) {
			Santa santa = santas[p];
			if(santa.out || santa.stack>0) continue;
			int dir = find_santa_dir(santa);
			if(dir!=-1) { // 움직일 방향 있으면 움직이기
				map[santa.r][santa.c]=0; // 원래 위치 0으로 표시
				
				int nr = santa.r + dr[dir];
				int nc = santa.c + dc[dir];
				if(map[nr][nc]==-1) { // 해당 위치에 루돌프가 있으면 충돌 발생
					santa.score += D;
					santa.stack = 2;
					int rev_dir = (dir+2)%4; // 반대방향
					collision(p,dr[rev_dir],dc[rev_dir],D-1); // 자신이 이동해온 반대 방향으로 D칸 이동 
				}else {
					santa.r = nr;
					santa.c = nc;
					map[santa.r][santa.c]=p;
				}
			}
		}
	}

내부적으로 산타가 움직일 위치를 결정할 find_santa_dir 함수를 호출합니다.

이동할 위치에 루돌프가 있으면 충돌이 발생하므로, collission함수를 호출합니다. 

이때 이동방향은 반대방향이므로 (dir+2)%4 연산을 통해 반대방향을 구현하였으며, collission함수의 마지막 매개변수는 D-1을 넘겨줘야 합니다.

왜냐하면 산타가 루돌프 위치에서 D칸 움직여야 하는데, 현재 산타 위치는 루돌프 바로 옆이기 때문입니다.

 

find_santa_dir 함수

static int find_santa_dir(Santa santa) {
		int dir = -1;
		
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->{
			if(o1[0]==o2[0]) {
				return (o1[1]-o2[1]);
			}
			return (o1[0]-o2[0]);
		});
		int r = santa.r;
		int c = santa.c;
		
		int origin_distance = (int)(Math.pow(r-rudolf[0],2) + Math.pow(c-rudolf[1], 2));
		
		for(int d=0;d<4;d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr<0 || nr>=N) continue;
			if(nc<0 || nc>=N) continue;
			if(map[nr][nc]>0) continue; // 다른 산타가 있는 경우
			int distance = (int)(Math.pow(nr-rudolf[0],2) + Math.pow(nc-rudolf[1], 2));
			if(distance < origin_distance) { // 원래 위치보다 가까워 지는 경우에만 qp에 넣음
				pq.offer(new int[] {distance,d});
			}
		}
		
		if(pq.size()>0) {
			int[] result = pq.poll();
			dir = result[1];
		}
		
		return dir;
	}

우선순위 큐를 활용하여 최단거리, 거리가 같으면 (상, 우, 하, 좌) 순서대로 우선순위를 결정했습니다.

 

기절 스택을 줄이는 함수(decrease_stack)

static void decrease_stack() {
		for(int p=1;p<=P;p++) {
			Santa santa = santas[p];
			if(santa.stack>0) {
				santa.stack -= 1;
			}
		}
	}

매턴 종료마다 해당 함수를 호출하여 기절 시 스택값으로 넘겨준 2를 1씩 감소시킵니다.. 사실 이 부분은 문제의 예시에서 힌트를 주고 있습니다.

 

산타들의 점수를 1점씩 올려주는 함수(add_score)

static void add_score() {
		for(int p=1;p<=P;p++) {
			Santa santa = santas[p];
			if(santa.out) continue;
			santa.score += 1;
		}
	}

산타가 라인에서 나가지 않았으면 점수를 1점 증가시킵니다.

 

알게된점

• 해당 문제를 풀면서 알게된 점은 2차원 배열에 객체를 직접 할당하지 않아도 된다는 점입니다.
  int[][] map과 같이 객체들의 번호를 할당하고, 실제 객체는 다른 배열에 저장하여 매칭하는 방식으로 자료구조를 활용할 수 있음을 알게되었습니다.
• 또한 여러 우선순위가 중첩된 경우 우선순위큐를 잘 활용해야 겠다고 느꼈습니다. 

 

전체코드

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


// 1. 루돌프 움직이기
// 가장 가까운 산타를 찾아야 함 (산타들의 정보를 저장하고 있어야 함)
// 해당 위치로 루돌프를 1칸 전진
// 산타와 루돌프가 충돌하는 경우를 구현
// 이때 루돌프끼리 충돌하는 경우도 구현(상호작용)

// 2. 산타 움직이기
// 루돌프와 가장 가까워 지는 방향으로 1칸 이동
// 다른 산타가 있는 칸은 움직이지 못함
// 루돌프와 가까워 지는 방법이 없다면 움직이지 않음
// 상 우 하 좌 우선순위에 맞춰 움직임
// 산타와 루돌프가 충돌하는 경우를 구현
// 이때 루돌프끼리 충돌하는 경우도 구현(상호작용)

class Santa implements Comparable<Santa>{
	int r,c;
	int d;
	int score, stack;
	boolean out;
	
	public Santa(int r,int c) {
		this.r = r;
		this.c = c;
	}
	
	public void updateDistance(int r,int c) {
		this.d = (int)(Math.pow(this.r-r,2) + Math.pow(this.c-c,2));
	}
	
	@Override
	public int compareTo(Santa o) {
		if(this.d==o.d) {
			if(this.r==o.r) {
				return -(this.c-o.c);
			}
			return -(this.r-o.r);
		}
		return (this.d-o.d);
	}
	
}

public class Main {
	
	static int N,M,P,C,D;
	static int[][] map; // N*N, 산타들의 번호, 루돌프 표시(-1)
	static Santa[] santas; // 1번 산타, 2번 산타의 정보를 저장
	static int[] rudolf; // 루돌프의 좌표
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	static int live_santa_cnt;
	
	static Santa find_nearest_santa() {
		PriorityQueue<Santa> pq = new PriorityQueue<>();
		
		for(int p=1;p<=P;p++) {// 산타들의 루돌프 까지의 거리 업데이트
			if(santas[p].out) continue;
			santas[p].updateDistance(rudolf[0],rudolf[1]); 
			pq.offer(santas[p]);
		}
		
		return pq.poll();
	}
	
	static void collision(int santa_num, int dr,int dc, int n) { 
		
		int r = santas[santa_num].r;
		int c = santas[santa_num].c;
		map[r][c] = 0; // 원래위치 0으로 표시
		
		int nr = r + dr*n;
		int nc = c + dc*n;
		
		santas[santa_num].r = nr;
		santas[santa_num].c = nc;
		
		if(nr<0 || nr>=N || nc<0 || nc>=N) {
			santas[santa_num].out = true;
			live_santa_cnt -= 1;
			return;
		}
		
		if(map[nr][nc]!=0) { // 또 다른 산타가 해당 위치에 있으면 dfs
			collision(map[nr][nc],dr,dc,1);
		}
		map[nr][nc] = santa_num; //이동한 위치에 산타번호 표시
	}
	
	static void move_rudolf() {
		Santa finded_santa = find_nearest_santa();
		int dc = 0;
		if(rudolf[1]>finded_santa.c) {
			dc = -1;
		}else if(rudolf[1]<finded_santa.c) {
			dc = 1;
		}
		int dr = 0;
		if(rudolf[0]>finded_santa.r) {
			dr = -1;
		}else if(rudolf[0]<finded_santa.r) {
			dr = 1;
		}
		
		map[rudolf[0]][rudolf[1]]=0; // 원래 위치 0으로 표시
		
		int nr = rudolf[0] + dr;
		int nc = rudolf[1] + dc;
		if(map[nr][nc]!=0) { // 산타가 있으면 충돌 발생
			int santa_num = map[nr][nc]; // 충돌이 발생하는 산타의 번호
			santas[santa_num].score += C;
			santas[santa_num].stack = 2;
			
			collision(santa_num,dr,dc,C); // santa_num의 산타를 dr,dc 방향으로 C칸 만큼 이동 
		}
		map[nr][nc]=-1; // 루돌프 이동
		rudolf[0] = nr; // 루돌프 좌표 갱신
		rudolf[1] = nc;
	}
	
	static int find_santa_dir(Santa santa) {
		int dir = -1;
		
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->{
			if(o1[0]==o2[0]) {
				return (o1[1]-o2[1]);
			}
			return (o1[0]-o2[0]);
		});
		int r = santa.r;
		int c = santa.c;
		
		int origin_distance = (int)(Math.pow(r-rudolf[0],2) + Math.pow(c-rudolf[1], 2));
		
		for(int d=0;d<4;d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr<0 || nr>=N) continue;
			if(nc<0 || nc>=N) continue;
			if(map[nr][nc]>0) continue; // 다른 산타가 있는 경우
			int distance = (int)(Math.pow(nr-rudolf[0],2) + Math.pow(nc-rudolf[1], 2));
			if(distance < origin_distance) { // 원래 위치보다 가까워 지는 경우에만 qp에 넣음
				pq.offer(new int[] {distance,d});
			}
		}
		
		if(pq.size()>0) {
			int[] result = pq.poll();
			dir = result[1];
		}
		
		return dir;
	}
	
	static void move_santa() {
		
		for(int p=1;p<=P;p++) {
			Santa santa = santas[p];
			if(santa.out || santa.stack>0) continue;
			int dir = find_santa_dir(santa);
			if(dir!=-1) { // 움직일 방향 있으면 움직이기
				map[santa.r][santa.c]=0; // 원래 위치 0으로 표시
				
				int nr = santa.r + dr[dir];
				int nc = santa.c + dc[dir];
				if(map[nr][nc]==-1) { // 해당 위치에 루돌프가 있으면 충돌 발생
					santa.score += D;
					santa.stack = 2;
					int rev_dir = (dir+2)%4; // 반대방향
					collision(p,dr[rev_dir],dc[rev_dir],D-1); // 자신이 이동해온 반대 방향으로 D칸 이동 
				}else {
					santa.r = nr;
					santa.c = nc;
					map[santa.r][santa.c]=p;
				}
			}
		}
	}
	static void decrease_stack() {
		for(int p=1;p<=P;p++) {
			Santa santa = santas[p];
			if(santa.stack>0) {
				santa.stack -= 1;
			}
		}
	}
	
	static void add_score() {
		for(int p=1;p<=P;p++) {
			Santa santa = santas[p];
			if(santa.out) continue;
			santa.score += 1;
		}
	}
	
	static void start() {
		
		for(int m=0;m<M;m++) {
			move_rudolf();
			move_santa();
			decrease_stack();
			add_score();
			
			if(live_santa_cnt==0) {
				return;
			}
		}
		
	}
	
	
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        
        map = new int[N][N];
        santas = new Santa[P+1];
        rudolf = new int[2];
        live_santa_cnt = P;
        
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<2;i++) {
        	rudolf[i] = Integer.parseInt(st.nextToken())-1;
        }
        map[rudolf[0]][rudolf[1]] = -1; // 루돌프는 -1
        
        for(int p=0;p<P;p++) {
        	st = new StringTokenizer(br.readLine());
        	int num,row,col;
        	num = Integer.parseInt(st.nextToken());
        	row = Integer.parseInt(st.nextToken())-1;
        	col = Integer.parseInt(st.nextToken())-1;
        	map[row][col] = num;
        	santas[num] = new Santa(row,col);
        }
        
        start();
        
        for(int p=1;p<=P;p++) {
        	System.out.print(santas[p].score+" ");
        }
        
        
        
    }

}