[BOJ 20056] 마법사 상어와 파이어볼

문제

• BOJ 20056
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

파이어볼의 정보인 좌표, 무게, 속도, 방향을 담은 Fireball클래스를 만들고, 리스트 타입의 2차원 배열에서 다음을 수행한다.

1. k초동안 map[][]을 돌면서 모든 파이어볼 이동을 시작한다.
   • move()에서 리스트에서 하나씩 파이어볼을 꺼내서 다음 좌표를 구한다. 이 때 주의할 점은 문제에서 1번 행,열과 N번 행,열이 연결되어있다고 했으므로 다음 좌표가 1보다 작거나 N보다 큰 경우 좌표 안에 들어올 수 있또록 처리해줘야한다.
   • 다음 좌표를 구하면 tmp[][]에 저장한다.
2. 한 칸에 여러 파이어볼이 있는 좌표는 divide()에서 합쳐주고 나누는 과정을 한다.
   • 문제에 제시된 대로 합친 질량, 속도, 방향을 구한다. 이 때, 구한 질량이 0이면 map에 넣지 않고 return한다.
3. k초가 끝나면 map[][]을 돌면서 남아있는 질량의 합을 출력한다.

이 문제에서 중요하게 생각할 것은 1번행,열과 N번 행,열이 연결되어있기 때문에 다음 좌표를 구할 때 이를 어떻게 처리해야할지, 그리고 파이어볼을 이동시킬 때 map[][]에 바로 담는것이 아니라 tmp[][]에 임시로 넣은 후에 map[][]을 초기화하고 차례로 tmp[][]에 있는 값을 넣어주어야 하는 것이다. 좌표에서 이동문제가 나오면 거의 이동후에 수행해야할 작업이 대부분인 것 같다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N,M,K;
	static List<Fireball>[][] map;
	static List<Fireball>[][] tmp;
	static int[][] dArr = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
	static int[] oddDrr = {1,3,5,7}; //홀수 방향
	static int[] evenDrr = {0,2,4,6}; //짝수 방향
	
	static class Fireball{
		int x, y, m, s, d;
		
		public Fireball(int x, int y, int m, int s, int d){
			this.x = x;
			this.y = y;
			this.m = m;
			this.s = s;
			this.d = d;
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = initMap(map);
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			map[x][y].add(new Fireball(x, y, m, s, d));
		}
		
		//k초 동안 시작
		for(int k=0; k<K; k++) {
			tmp = initMap(tmp); //이동 후 상태 저장
			
			//1. 모든 파이어볼 이동 시작
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					if(map[i][j].size() > 0) move(map[i][j]);
				}
			}
			
			map = initMap(map);
			//2. 이동 후 여러개인 칸은 합치고 나누기
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					if(tmp[i][j].size() == 1) map[i][j] = tmp[i][j];
					else if(tmp[i][j].size() > 1) divide(tmp[i][j], i, j);
				}
			}
		}
		
		//남아있는 질량의 합 구하기
		System.out.println(restSum());
	}

	private static int restSum() {
		int sum = 0;
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(map[i][j].size() == 0) continue;
				for(int k=0; k<map[i][j].size(); k++) {
					Fireball f = map[i][j].get(k);
					sum += f.m;
				}
			}
		}
		return sum;
	}

	private static void divide(List<Fireball> list, int x, int y) {
		int cnt = list.size(); //파이어볼 개수
		int mSum = 0; //질량 합
		int sSum = 0; //속력 합
		int[] sDir = new int[cnt]; //방향 
		
		for(int i=0; i<list.size(); i++) {
			Fireball f = list.get(i);
			mSum += f.m;
			sSum += f.s;
			sDir[i] = f.d;
		}
		
		//방향 구하기
		boolean odd = false; //홀수
		boolean even = false; //짝수
		
		for(int i=0; i<cnt; i++) {
			if(sDir[i] % 2 == 0) even = true;
			else odd = true;
		}
		
		if(!(odd && even)) { //모두 홀수이거나 짝수 => 짝수방향
			sDir = evenDrr;
		}else sDir = oddDrr;
		
		//이제 나누기
		if(mSum / 5 == 0) return; //질량이 0이면 소멸
		for(int i=0; i<4; i++) {
			map[x][y].add(new Fireball(x, y, mSum / 5, sSum / cnt, sDir[i]));
		}
	}

	private static void move(List<Fireball> list) {
		for(int i=0; i<list.size(); i++) {
			Fireball f = list.get(i);
			
			//1-N은 연결되어 있음 => 체크 주의!!
			int nx = (f.x + f.s*dArr[f.d][0]) % N;
			int ny = (f.y + f.s*dArr[f.d][1]) % N;
			if(nx < 1) nx += N;
			if(ny < 1) ny += N;
            if(nx > N) nx -= N;
			if(ny > N) ny -= N;
			
			if(nx>=1 && nx<=N && ny>=1 && ny<=N) {
				tmp[nx][ny].add(new Fireball(nx, ny, f.m, f.s, f.d));
			}
		}
	}
	
	private static List<Fireball>[][] initMap(List<Fireball> arr[][]) {
		arr = new ArrayList[N+1][N+1];
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				arr[i][j] = new ArrayList<>();
			}
		}
		return arr;
	}
}