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

[문제링크]

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

 

0. 빠트린 부분 없이 잘 구현하면 되는 구현문제 (불가능)

 

1. 파이어볼 질량은 겹친 파이어볼이 분리될때에만 변경된다

• 초기 질량합을 구해서 유지, 파이어볼 분리 작업마다 질량합을 수정한다

 

2. Fireball은 위치 + 질량/방향/속도 값을 가지며, 끊임없이 움직인다

• 배열 : 여러 fireball을 저장하기 힘들다
• List : fireball을 제거/이동하기 힘들다
• Stack : push/pop으로 쉽게 이용 가능
• 이런 이유로 Stack 사용

 

3. Stack을 가지는 class를 만들어 2차원 배열로 구현, Fireball의 위치 값을 표현했다

 

4. 이동 이후 Stack의 size가 1보다 크면 분리 작업 수행

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main{
	static class Fireball{
		Stack<int[]>balls;
		public Fireball() {
			balls= new Stack<>();
		}
	}
	static int[][] dir= new int[][] {
		{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}
	};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = pint(st.nextToken());
		int M = pint(st.nextToken());
		int K = pint(st.nextToken());
		int totalW=0;
		
		Fireball[][] fireballs = new Fireball[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				fireballs[i][j]=new Fireball();
			}
		}
		
		for (int i = 0; i < M; i++) {
			int w;
			st = new StringTokenizer(br.readLine(), " ");
			fireballs[pint(st.nextToken())-1][pint(st.nextToken())-1]
					.balls.add(new int[] {w=pint(st.nextToken()),pint(st.nextToken()),pint(st.nextToken())});
			totalW+=w;
		}
		
		for (int i = 0; i < K; i++) {
			List<int[]> l = new ArrayList<>();
			//이동 시작
			for (int j = 0; j < N; j++) {
				for (int j2 = 0; j2 < N; j2++) {
					while(!fireballs[j][j2].balls.isEmpty()) {
						int[] ball = fireballs[j][j2].balls.pop();
						int x = j + dir[ball[2]][0]*ball[1]+N;
						int y = j2+ dir[ball[2]][1]*ball[1]+N;
						x%=N; if(x<0)x+=N;
						y%=N; if(y<0)y+=N;
						l.add(new int[] {x,y,ball[0],ball[1],ball[2]});
					}
				}
			}
			for (int[] b : l) {
				fireballs[b[0]][b[1]].balls.add(new int[] {b[2],b[3],b[4]});
			}
			
			//이동 끝
			for (int j = 0; j < N; j++) {
				for (int j2 = 0; j2 < N; j2++) {
					int size=0;
					if( (size = fireballs[j][j2].balls.size()) >1) {
						boolean same = true;
						int[] ball=fireballs[j][j2].balls.pop();
						int ballW = ball[0];//m,s,d
						int ballS = ball[1];
						int fstDir = ball[2]%2;
						int newDir=0;
						
						for (int o = 1; o < size; o++) {
							ball=fireballs[j][j2].balls.pop();
							ballW += ball[0];//m,s,d
							ballS += ball[1];
							if(fstDir != ball[2]%2)same=false;
						}
						totalW-=ballW;
						ballW/=5;
						ballS/=size;
						totalW+=ballW*4;
						
						if(ballW==0)continue;//0이면 소멸
						if(!same)newDir=1;
						for (int o = 0; o < 4; o++) {
							fireballs[j][j2].balls.add(new int[] {ballW, ballS, newDir});
							newDir+=2;
						}
					}
				}
			}//겹친 파이어볼 분리 끝
			
		}//K번 실행 끝
		System.out.println(totalW);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면