[JAVA] CodeTree 싸움 땅

snowball🐰 2023. 4. 7. 11:40

https://www.codetree.ai/training-field/frequent-problems/battle-ground/description?page=3&pageSize=20&username=

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

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

💡 시뮬레이션 문제이다. BFS, DFS 등은 사용하지 않는다.

1. 여러 자료구조를 사용하여 문제를 해결할 것이다.
2. 사람, 총, 현재 위치에 있는 사람의 번호 세가지를 모두 따로 저장해두었으므로 정보가 바뀔때
모두를 갱신시켜야 한다!
3. 문제 설명이 조금 헷갈릴 수 있는데 1번이 이동하여 2번과 대결한 뒤 2번이 져서 다른 위치로 이동하여도
바로 2번은 자신의 차례에 이동을 진행 해야한다.

전체 코드

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

public class Main {
	static int N, M, K;
	static ArrayList<Integer>[][] gun; // 해당 위치의 총 정보. 없으면 size가 0
	static int[][] people; // 해당 위치의 사람 정보 (person의 number를 저장함)
	static class person{
		int number; // 번호
		int power; // 초기 능력치
		int gun; // 가진 총의 공격력 0이면 총이 없다.
		int d; // 방향
		int x; int y;
		public person(int number, int x, int y, int d, int power) {
			super();
			this.number = number;
			this.power = power;
			this.d = d;
			this.x = x;
			this.y = y;
		}
	}
	static ArrayDeque<person> p;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
	static int[] score;
    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        N = Integer.parseInt(st.nextToken()); //격자 크기
        M = Integer.parseInt(st.nextToken()); //플레이어수
        K = Integer.parseInt(st.nextToken()); //라운드 수
        score = new int[M+1]; // score[1] = 1번 플레이어의 점수
        gun = new ArrayList[N][N];
        people = new int[N][N];
        for(int i=0; i<N; i++)
        	for(int j=0; j<N; j++)
        		gun[i][j] = new ArrayList<>();
        
        for(int i=0; i<N; i++) {
        	st = new StringTokenizer(bf.readLine(), " ");
        	for(int j=0; j<N; j++) {
        		int g = Integer.parseInt(st.nextToken());
        		if(g != 0)
        			gun[i][j].add(g);
        	}
        }
        p = new ArrayDeque<>();
        
        for(int i=1; i<=M; i++) {
        	st = new StringTokenizer(bf.readLine(), " ");
        	int x = Integer.parseInt(st.nextToken())-1;
        	int y = Integer.parseInt(st.nextToken())-1;
        	int d = Integer.parseInt(st.nextToken());
        	int s = Integer.parseInt(st.nextToken());
        	people[x][y] = i;
        	p.offer(new person(i, x, y, d, s));
        }
        int time = 0;
        while(++time <= K) {
        	move_people();
        }
        for(int i=1; i<=M; i++)
        	sb.append(score[i]).append(" ");
        
        System.out.println(sb);
    }
    static void move_people() {
    	int cnt = 0;
    	while(++cnt <= M) {
    		person player = p.poll();
    		int nx = player.x+dx[player.d];
    		int ny = player.y+dy[player.d];
    		if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
    			player.d += 2;
    			player.d %= 4;
    			nx = player.x+dx[player.d];
        		ny = player.y+dy[player.d];
    		}
    		if(people[nx][ny] == 0) { // 해당 위치에 사람이 없는 경우
    			if(gun[nx][ny].size() != 0) { // 해당 위치에 총이 있는 경우
    				int max = player.gun; int max_idx = -1;
    				for(int i=0; i<gun[nx][ny].size(); i++) {
    					int g = gun[nx][ny].get(i);
    					if(max < g) {
    						max = g; max_idx = i;
    					}
    				}
    				if(max_idx != -1) { // 총 변경
    					gun[nx][ny].remove(max_idx);
    					if(player.gun != 0) gun[nx][ny].add(player.gun);
    					player.gun = max;
    				}
    			}
    			people[player.x][player.y] = 0; // 이동 전 위치 흔적 지우기
    			people[nx][ny] = player.number; // 이동하기
    			player.x = nx;
    			player.y = ny; // 좌표 변경
    			p.offer(player);
    		}
    		else { // 있는 경우
    			int vs = people[nx][ny]; // 대결 상대의 number
    			people[player.x][player.y] = 0; // 이미 이동했으므로 직전 위치 흔적 지움
    			player.x = nx;
    			player.y = ny; //이미 이동했으므로 player 좌표 값 수정
    			fire(vs, player);
    		}
    	}
    }
    static void fire(int vs, person now) {
    	int cnt = 0;
    	while(++cnt < M) { // 현재 플레이어가 잠깐 나와있으므로 M-1번 진행
    		person v = p.poll();
    		if(v.number != vs) p.offer(v); // 대결상대가 아니면 다시 넣어주기
    		else {
    			if(v.power + v.gun < now.power + now.gun || (v.power + v.gun == now.power + now.gun && v.power < now.power)) {
    				// v가 졌음
    				score[now.number] += (now.power + now.gun) - (v.power + v.gun); // 점수 증가시키기
    				people[v.x][v.y] = now.number; // 해당 위치에는 now가 남음
    				
    				if(now.gun < v.gun) { // v가 해당 격자에서 가장 큰 총을 가지고 있을 것이므로 v하고만 비교하기
    					if(now.gun != 0) gun[now.x][now.y].add(now.gun);
    					now.gun = v.gun;
    				}
    				else
    					if(v.gun != 0)
    						gun[v.x][v.y].add(v.gun); // v가 총을 가지고 있었다면 총을 내려놓기
    				
    				v.gun = 0;
    				for(int d=0; d<4; d++) {
    					int nx = v.x + dx[(v.d + d) % 4];
    					int ny = v.y + dy[(v.d + d) % 4];
    					if(nx < 0 || ny < 0 || nx >= N || ny >= N || people[nx][ny] != 0) continue; // 격자에서 벗어나거나 사람이 있는 경우는 다른 격자 찾기
    					people[nx][ny] = v.number;
    					v.x = nx; v.y = ny;
    					v.d = (v.d + d) % 4; // 방향이 바뀌었으므로 좌표와 이동 방향 갱신
    					break;
    				}
    				
    				int max = 0; int max_idx = -1;
    				for(int i=0; i<gun[v.x][v.y].size(); i++) {
    					int g = gun[v.x][v.y].get(i);
    					if(max < g) {
    						max = g; max_idx = i;
    					}
    				}
    				if(max_idx != -1) {
    					gun[v.x][v.y].remove(max_idx);
    					v.gun = max;
    				}
    				p.offer(v); // v의 모든 정보가 갱신되었으므로 queue에 넣는다.
    			}
    			else {
    				// v가 이겼음
    				score[v.number] += (v.power + v.gun) - (now.power + now.gun);
    				
    				// v는 이미 칸의 가장 공격력이 높은 총을 가지고 있으므로 진 플레이어의 총만 비교
    				if(now.gun > v.gun) {
    					if(v.gun != 0) gun[v.x][v.y].add(v.gun);
    					v.gun = now.gun;
    				}
    				else if(now.gun != 0) 
    					gun[v.x][v.y].add(now.gun); // 진 플레이어 총 내려놓음
    				now.gun = 0;
    				p.offer(v); // v는 총의 정보를 제외하고 갱신할 것이 없으므로 queue에 넣어준다.
    				
    				for(int d=0; d<4; d++) {
    					int nx = now.x + dx[(now.d + d) % 4];
    					int ny = now.y + dy[(now.d + d) % 4];
    					if(nx < 0 || ny < 0 || nx >= N || ny >= N || people[nx][ny] != 0) continue;
    					people[nx][ny] = now.number;
    					now.x = nx; now.y = ny;
    					now.d = (now.d + d) % 4;
    					break;
    				}
    				int max = 0; int max_idx = -1;
    				for(int i=0; i<gun[now.x][now.y].size(); i++) {
    					int g = gun[now.x][now.y].get(i);
    					if(max < g) {
    						max = g; max_idx = i;
    					}
    				}
    				if(max_idx != -1) {
    					gun[now.x][now.y].remove(max_idx);
    					now.gun = max;
    				}
    			}
    		}
    	}
    	p.offer(now); // 마지막에 넣어주어야 원하는 순서 유지
    }
}

한 줄 씩 살펴보자

static int N, M, K;
static ArrayList<Integer>[][] gun; // 해당 위치의 총 정보. 없으면 size가 0
static int[][] people; // 해당 위치의 사람 정보 (person의 number를 저장함)
static class person{
	int number; // 번호
	int power; // 초기 능력치
	int gun; // 가진 총의 공격력 0이면 총이 없다.
	int d; // 방향
	int x; int y;
	public person(int number, int x, int y, int d, int power) {
		super();
		this.number = number;
		this.power = power;
		this.d = d;
		this.x = x;
		this.y = y;
	}
}
static ArrayDeque<person> p;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static int[] score;

사람 객체를 만들었고, 사람 객체를 관리할 ArrayDeque을 선언하였다. 이때 deque은 person num 순서대로를 유지하도록 하였다.

이차원 배열 people을 통해 현재 위치한 사람의 번호를 저장하였다. 현재 위치에 사람이 있는지 빠르게 파악하기 위함이다.

static void move_people() {
	int cnt = 0;
	while(++cnt <= M) {
		person player = p.poll();
		int nx = player.x+dx[player.d];
		int ny = player.y+dy[player.d];
		if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
			player.d += 2;
			player.d %= 4;
			nx = player.x+dx[player.d];
    		ny = player.y+dy[player.d];
		}
		if(people[nx][ny] == 0) { // 해당 위치에 사람이 없는 경우
			if(gun[nx][ny].size() != 0) { // 해당 위치에 총이 있는 경우
				int max = player.gun; int max_idx = -1;
				for(int i=0; i<gun[nx][ny].size(); i++) {
					int g = gun[nx][ny].get(i);
					if(max < g) {
						max = g; max_idx = i;
					}
				}
				if(max_idx != -1) { // 총 변경
					gun[nx][ny].remove(max_idx);
					if(player.gun != 0) gun[nx][ny].add(player.gun);
					player.gun = max;
				}
			}
			people[player.x][player.y] = 0; // 이동 전 위치 흔적 지우기
			people[nx][ny] = player.number; // 이동하기
			player.x = nx;
			player.y = ny; // 좌표 변경
			p.offer(player);
		}
		else { // 있는 경우
			int vs = people[nx][ny]; // 대결 상대의 number
			people[player.x][player.y] = 0; // 이미 이동했으므로 직전 위치 흔적 지움
			player.x = nx;
			player.y = ny; //이미 이동했으므로 player 좌표 값 수정
			fire(vs, player);
		}
	}
}

move_people()을 통해 모든 사람들을 조건에 맞게 이동시켰다.

M명이 이동하므로 횟수는 M번이 된다.

people이 0이면 이동 위치에 사람이 없다는 뜻이므로 해당 위치에서 총을 갱신한다.

이 이동을 통해 person의 x, y, (d), gun이 갱신됨을 유의하자! 또한 person의 위치가 갱신되었기 때문에 이차원 배열 people의 정보도 갱신해야 한다.

해당 위치에서 총의 정보를 갱신시킬 때 max의 값을 player.gun으로 주지않고 0으로 주게 되면 player가 공격력이 더 큰 총을 가지고 있더라도 해당 위치에서 가장 큰 공격력을 가진 총으로 바뀌게 된다. → 주의

만약 이동 위치에 사람이 있다면 해당 player의 정보를 갱신하고 fire함수로 처리하였다.

static void fire(int vs, person now) {
	int cnt = 0;
	while(++cnt < M) { // 현재 플레이어가 잠깐 나와있으므로 M-1번 진행
		person v = p.poll();
		if(v.number != vs) p.offer(v); // 대결상대가 아니면 다시 넣어주기
		else {
			if(v.power + v.gun < now.power + now.gun || (v.power + v.gun == now.power + now.gun && v.power < now.power)) {
				// v가 졌음
				score[now.number] += (now.power + now.gun) - (v.power + v.gun); // 점수 증가시키기
				people[v.x][v.y] = now.number; // 해당 위치에는 now가 남음
				
				if(now.gun < v.gun) { // v가 해당 격자에서 가장 큰 총을 가지고 있을 것이므로 v하고만 비교하기
					if(now.gun != 0) gun[now.x][now.y].add(now.gun);
					now.gun = v.gun;
				}
				else
					if(v.gun != 0)
						gun[v.x][v.y].add(v.gun); // v가 총을 가지고 있었다면 총을 내려놓기
				
				v.gun = 0;
				for(int d=0; d<4; d++) {
					int nx = v.x + dx[(v.d + d) % 4];
					int ny = v.y + dy[(v.d + d) % 4];
					if(nx < 0 || ny < 0 || nx >= N || ny >= N || people[nx][ny] != 0) continue; // 격자에서 벗어나거나 사람이 있는 경우는 다른 격자 찾기
					people[nx][ny] = v.number;
					v.x = nx; v.y = ny;
					v.d = (v.d + d) % 4; // 방향이 바뀌었으므로 좌표와 이동 방향 갱신
					break;
				}
				
				int max = 0; int max_idx = -1;
				for(int i=0; i<gun[v.x][v.y].size(); i++) {
					int g = gun[v.x][v.y].get(i);
					if(max < g) {
						max = g; max_idx = i;
					}
				}
				if(max_idx != -1) {
					gun[v.x][v.y].remove(max_idx);
					v.gun = max;
				}
				p.offer(v); // v의 모든 정보가 갱신되었으므로 queue에 넣는다.
			}

위아래 내용은 같으므로 위만 설명하겠다.

먼저 대결 상대인 v를 찾아준다. deque의 순서 유지를 위해 뺀 다음 바로 맨 뒤에 넣어주어야 한다.

now 즉 현재 플레이어가 이긴다면 점수를 갱신한다.

또한 해당 위치에 잔류할 플레이어는 now이므로 people도 갱신한다.

이때 v는 자신의 총을 두고 가게 된다. v는 이미 해당 칸에서 갱신된 총을 들고 있을 것이므로 가장 큰 총을 들고 있다. 그러므로 player는 v의 총만 비교해주면 된다.

v는 총을 내려놨으므로 v.gun은 0이 되어야 한다

문제에서 제시된 대로 v의 위치를 옮기고 x, y, d, people을 갱신한다.

v는 이동한 위치에서 가장 큰 총을 들게 된다. move_people에서처럼 총을 찾아준다. 이때 max를 v.gun으로 주어도 되고 0으로 주어도 된다. 왜냐하면 v는 총을 들고있지 않기 때문.

now의 승패에 관련없이 now는 함수 return 직전에 deque에 넣어주어야 한다!!! → ⭐순서유지