[백준] JAVA - 20056. 마법사 상어와 파이어볼

https://www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

생각

같은좌표에 있는 파이어볼을 나눠줄때 혼자 있는 파이어볼을 고려하지 않고 헤메다가 두번째 시도만에 풀었습니다..!!

- 큐를 사용하여 각 단계별로 파이어볼의 이동을 동시에 처리해줬습니다. 

- 파이어볼 클래스를 생성하여 파이어볼 이동함수와 합치는 함수를 내부에서 따로 구현해줬습니다.

 

move 함수는 파이어볼이 다음에 움직일 좌표를 계산합니다. 이때 '1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.' 라고 문제에서 나와있기 때문에 나머지 연산을 통해 다음 좌표를 계산해줬습니다. (this.y = (this.y + (dy[d]*s)%N + N)%N 에서 N을 더해주면 음수일때를 고려하지 않아도 됩니다)

 

merge함수를 통해 특정 좌표에서 합쳐지는 갯수, 총 질량, 총 속력, 방향 변환 여부 모두를 누적해서 확인합니다.

 

1. 큐에 파이어볼 객체를 추가시켜줍니다.

2. 큐의 사이즈만큼 반복문을 돌아 각 단계별로 파이어볼을 동시에 이동시켜줍니다.

3. 이동이 끝나면 합쳐져야 할 파이어볼들을 합쳐줍니다. 파이어볼의 좌표값에 해당하는 map이 null이라면 map[y][x] 에 파이어볼 객체를 넣어줍니다. null 이 아니라면 누적해야 한다는 뜻이므로 map[y][x]에 merge 함수로 파이어볼을 합쳐줍니다.  

4. 합쳐진 파이어볼을 분리합니다. map 을 반복문을 돌면서 map[y][x]!=null 이고 mergeCnt가 1 이상인곳을 탐색한뒤 나뉜 질량이 0이상이라면 새로운 파이어볼을 생성하여 큐에 추가시켜줍니다. 이때 합쳐지지 않고 단독으로 존재하는 파이어볼은 그대로 큐에 넣어줘야 합니다!

5. 명령어가 1 감소되고 K가 0이 될때까지 2~5번 작업을 반복합니다.

6. 큐에 있는 파이어볼 객체들의 질량을 누적하여 출력합니다.

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_마법사상어와파이어볼Re {
	static class Fireball{
		int y,x,m,s,d; // y x 질량 속도 방향
		int mergeCnt = 1; // 몇개합쳐졌는지
		boolean allSameDir = true; // 모두 짝수이거나 모두 홀수일때
		
		public Fireball(int y, int x, int m, int s, int d) {
			super();
			this.y = y;
			this.x = x;
			this.m = m;
			this.s = s;
			this.d = d;
		}
		public void move() {
			this.y = (this.y + (dy[d]*s)%N + N)%N;
			this.x = (this.x + (dx[d]*s)%N + N)%N;
		}
		
		public void merge(Fireball other) {
			this.m += other.m;
			this.s += other.s;
			mergeCnt++;
			if(allSameDir && (this.d%2 != other.d%2)) {
				allSameDir = false; // 한번이라도 달라지면 다른것
			}
		}
		@Override
		public String toString() {
			return "Fireball [y=" + y + ", x=" + x + ", m=" + m + ", s=" + s + ", d=" + d + ", mergeCnt=" + mergeCnt
					+ ", allSameDir=" + allSameDir + "]";
		}

	}
	static int N, M, K;
	static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
	static Queue<Fireball> q;
	static Fireball[][] map;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] init = br.readLine().split(" ");
		N = Integer.parseInt(init[0]); // 맵 크기
		M = Integer.parseInt(init[1]); // 파이어볼 개수
		K = Integer.parseInt(init[2]); // 명령어 횟수
		
		map = new Fireball[N][N];
		
		q = new LinkedList<>();
		
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int y = Integer.parseInt(st.nextToken())-1;
			int x = Integer.parseInt(st.nextToken())-1;
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			Fireball fb = new Fireball(y, x, m, s, d);
			q.offer(fb);
		}
		
		while(!q.isEmpty()) {
			if(K==0) break;
			int size = q.size();
			while(size-- > 0) {
				Fireball now = q.poll();
				//파이어볼 이동
				now.move();
				if(map[now.y][now.x] == null) {
					map[now.y][now.x] = now;
				}else {
					map[now.y][now.x].merge(now);//누적해서 합쳐주기
				}
			}//이동 끝
			//분리하기
			split();
			K--;
		}
		
		int ans=0;
		while(!q.isEmpty()) {
			ans += q.poll().m;
		}
		System.out.println(ans);
	}
	
	private static void split() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] != null) {
					//합치기
					Fireball fb = map[i][j];		
					map[i][j] = null; //원래 좌표는 지워주고
					if(fb.mergeCnt > 1) {
						int newM = fb.m/5;
						int newS = fb.s/fb.mergeCnt;
						if(newM > 0) {
							if(fb.allSameDir) {
								for (int d = 0; d < 4; d++) {
									q.add(new Fireball(fb.y, fb.x, newM, newS, d*2));
								}
							}else {
								for (int d = 0; d < 4; d++) {
									q.add(new Fireball(fb.y, fb.x, newM, newS, d*2+1));
								}
							}
							
						}
					}else {
						q.add(fb); //혼자 있는것도 큐에 넣어주기 
					}
				}
			}
		}
		
	}
}