[코드트리] 삼성 SW 역량테스트 2023 하반기 오후 1번 문제

삼성 SW 역량테스트 2023 하반기 오후 1번 문제

 

실제 테스트에서는 못 풀고나왔는데, 다시 풀어보려고하니 역시나 어려웠다.

(19:16 ~ 22:38)

 

이런 구현문제는 디버깅도 잘해야겠다.

 

정석적으로 못 푼 것 같은데, 다른 코드도 보면서 부족한 부분을 채워야겠다.

 

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

 

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

 

 

package codetree;
import java.io.*;
import java.util.*;


public class SS01 {
	static class Pos{
		int y, x, score=0;
		int suspend = 0;
		boolean isDie = false;
		Pos(int y, int x, int score){
			this.y = y;
			this.x = x;
			this.score = score;
		}
		
		Pos(int y, int x){
			this.y = y;
			this.x = x;
		}
		
		public void print() {
			System.out.printf("[%d][%d]\n", this.y, this.x);
		}
		@Override
		public String toString() {
			return String.format("[%d][%d]: %d %d %s \n", y, x, score, suspend, (isDie? "DIE": "ALIVE"));
			
		}
	}
	static final int Rudol = 100;
	static final int rDir = 8;
	static final int Dir = 4;
	
	static int[] rdy = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] rdx = {0, 1, 1, 1, 0, -1, -1, -1};
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, 1, 0, -1};
	
	static int N, M, P, C, D;
	static int[][] board;
	
	static Pos rudolf;
	static Pos[] santas;
    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());
        
        santas = new Pos[P];
        st = new StringTokenizer(br.readLine());
        rudolf = new Pos(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
        for(int i=0; i<P; ++i) {
        	st = new StringTokenizer(br.readLine());
        	santas[Integer.parseInt(st.nextToken())-1]= new Pos(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
        }
        
        for(int m=0; m<M; ++m) {
        	moveRudolf();
        	moveSantas();
        	if(isAllDie()) break;
        }
        
       
        for(int i=0; i<P; ++i) {
        	System.out.print(santas[i].score+" ");
        }
        
    }

	private static void moveSantas() {
		for(int i=0; i<P; ++i) {
			if(santas[i].isDie) continue;
			if(santas[i].suspend>0) {
				--santas[i].suspend;
				continue;
			}
			int minDistDir = -1;
			int oriDist = (rudolf.y-santas[i].y)*(rudolf.y-santas[i].y) + (rudolf.x-santas[i].x)*(rudolf.x-santas[i].x);
			int dist = oriDist;
			for(int d=0; d<Dir; ++d) {
				int ny = santas[i].y + dy[d];
				int nx = santas[i].x + dx[d];
				if(!inRange(ny, nx)) continue;
				if(getCrushedIdx(ny, nx) != -1) continue;
				int tempDist = (rudolf.y - ny)*(rudolf.y - ny) + (rudolf.x - nx)*(rudolf.x - nx);
				if(tempDist<dist || tempDist == oriDist) {
					dist = tempDist;
					minDistDir = d;
				}
			}
			if(minDistDir != -1) {
				santas[i].y = santas[i].y + dy[minDistDir];
				santas[i].x = santas[i].x + dx[minDistDir];
				
				if(rudolf.y == santas[i].y && rudolf.x == santas[i].x) {
					crush(i, i, minDistDir);
				}
			}
		}
	}
	private static void moveRudolf() {
		int targetIdx = -1;
		int minDist = Integer.MAX_VALUE;
		for(int i=0; i<P; ++i) { // 가장 가까운 산타 고르기 
			if(santas[i].isDie == true) continue; // 탈락한 산타 건너뛰기 
			
			int dist = (rudolf.y-santas[i].y)*(rudolf.y-santas[i].y) + (rudolf.x-santas[i].x)*(rudolf.x-santas[i].x);
			if(dist < minDist) {
				minDist = dist;
				targetIdx = i;
			}else if(dist == minDist) {
				if(santas[targetIdx].y < santas[i].y) {
					targetIdx = i;
				}else if(santas[targetIdx].y == santas[i].y && santas[targetIdx].x < santas[i].x) {
					targetIdx = i;
				}
			}
		}// for end
		
		int goDir = -1;
		minDist = Integer.MAX_VALUE;
		Pos target = santas[targetIdx];
		for(int i=0; i<rDir; ++i) {
			int ny = rudolf.y + rdy[i];
			int nx = rudolf.x + rdx[i];
			if(!inRange(ny, nx)) continue;
			
			int dist = (ny-target.y)*(ny-target.y) + (nx-target.x)*(nx-target.x);
			if(dist < minDist) {
				minDist = dist;
				goDir = i;
			}
		}
		rudolf.y = rudolf.y + rdy[goDir];
		rudolf.x = rudolf.x + rdx[goDir];
		if(rudolf.y == target.y && rudolf.x == target.x) {
			crush(Rudol, targetIdx, goDir);
		}
		
		
		
	}
	private static void crush(int who, int targetIdx, int dir) {
		if(who == Rudol) {
			santas[targetIdx].score = santas[targetIdx].score + C;
			int ny = santas[targetIdx].y + (rdy[dir] * C);
			int nx = santas[targetIdx].x + (rdx[dir] * C);
			if(!inRange(ny, nx)) {
				santas[targetIdx].y = -1;
				santas[targetIdx].x = -1;
				santas[targetIdx].isDie = true;
			}else {
				int crushedIdx = getCrushedIdx(ny, nx);
				santas[targetIdx].y = ny;
				santas[targetIdx].x = nx;
				santas[targetIdx].suspend = 2; // 기절 
				if(crushedIdx != -1) {
					interact(who, crushedIdx, dir);
				}
			}
		}else { // 산타 => 루돌프 
			santas[targetIdx].score = santas[targetIdx].score + D;
			dir = (dir + 2) % 4;
			int ny = santas[targetIdx].y + (dy[dir] * D);
			int nx = santas[targetIdx].x + (dx[dir] * D);
			if(!inRange(ny, nx)) {
				santas[targetIdx].y = -1;
				santas[targetIdx].x = -1;
				santas[targetIdx].isDie = true;
			}else {
				int crushedIdx = getCrushedIdx(ny, nx);
				santas[targetIdx].y = ny;
				santas[targetIdx].x = nx;
				santas[targetIdx].suspend = 1; // 기절 
				if(crushedIdx != -1) {
					interact(who, crushedIdx, dir);
				}
			}
		}
	}
	
	
	private static void interact(int who, int idx, int dir) {
		int ny = 0, nx = 0;
		if(who == Rudol) {
			ny = santas[idx].y + rdy[dir];
			nx = santas[idx].x + rdx[dir];
		}else {
			ny = santas[idx].y + dy[dir];
			nx = santas[idx].x + dx[dir];
		}
		
		if(!inRange(ny, nx)) {
			santas[idx].isDie = true;
			santas[idx].y = santas[idx].x = -1;
		}else {
			int crushedIdx = getCrushedIdx(ny, nx);
			santas[idx].y = ny;
			santas[idx].x = nx;
			if(crushedIdx != -1) {
				interact(who, crushedIdx, dir);
			}
		}
		
	}
	private static int getCrushedIdx(int y, int x) {
		for(int i=0; i<P; ++i) {
			if(santas[i].y == y && santas[i].x == x) {
				return i;
			}
		}
		return -1;
	}
	private static boolean inRange(int y, int x) {
		return 0<= y && y<N && 0<=x && x<N;
	}
	
	private static boolean isAllDie() {
		int num = 0;
		for(int i=0; i<P; ++i) {
			if(santas[i].isDie) {
				++num;
			}else {
				santas[i].score=santas[i].score + 1;
			}
			
		}
		if(num == P) return true;
		return false;
	}
}