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

https://namhandong.tistory.com/214

 

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

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

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class P20056 {
	static int N, M, K;
	static Info[][] board;
	static List<FireBall> li=new ArrayList<>();
	static int[] dr= {-1, -1, 0,1,1,1,0,-1};
	static int[] dc= {0, 1,1,1,0,-1,-1,-1};
	public static void main(String[] args) throws IOException {
		String str;
		String[] arr;
		int answer=0;
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		K=sc.nextInt();
		int r,c,m,s,d;
		for (int i=0; i<M; i++) {
			r=sc.nextInt();
			c=sc.nextInt();
			m=sc.nextInt();
			s=sc.nextInt();
			d=sc.nextInt();
			li.add(new FireBall(r,c,m,s,d));
		}
		for (int i=0; i<K; i++) {
			makeBoard();
			move();
			makeFireBallList();
		}
		for (int i=0; i<li.size(); i++) {
			answer+=li.get(i).m;
		}
		System.out.println(answer);
	}
	

	public static void makeBoard() {
		board=new Info[N+1][N+1];
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				board[i][j]=new Info(new ArrayList<FireBall>());
			}
		}
	}
	
	public static void move() {
		int next_r, next_c;
		for (int i=0; i<li.size(); i++) {
			FireBall fb=li.get(i);
			next_r=fb.r;
			next_c=fb.c;
			for (int c=0; c<fb.s; c++) {
				next_r+=dr[fb.d];
				next_c+=dc[fb.d];
				if (next_r<=0) {
					next_r+=N;
				}
				else if (next_r>N) {
					next_r-=N;
				}
				if (next_c<=0) {
					next_c+=N;
				}
				else if (next_c>N) {
					next_c-=N;
				}	
			}
			fb.r=next_r;
			fb.c=next_c;
			board[next_r][next_c].fbs.add(fb);
		}
	}
	
	public static void makeFireBallList() {
		List<FireBall> temp=new ArrayList<>();
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				if (board[i][j].fbs.size()>1) {
					int msum=0;
					int ssum=0;
					int len=board[i][j].fbs.size();
					int odd=0;
					int even=0;
					for (FireBall fb: board[i][j].fbs) {
						msum+=fb.m;
						ssum+=fb.s;
						if (fb.d%2==0) {
							even++;
						}
						else {
							odd++;
						}
					}
					int nm=msum/5;
					int ns=ssum/len;
					if (nm==0) {
						continue;
					}
					if (even==len || odd==len) {
						for (int d=0; d<8; d+=2) {
							temp.add(new FireBall(i,j,nm, ns, d));
						}
					}
					else{
						for (int d=1; d<9; d+=2) {
							temp.add(new FireBall(i,j,nm, ns, d));
						}
					}
				}
				else if (board[i][j].fbs.size()==1) {
					temp.add(board[i][j].fbs.get(0));
				}
			}
		}
		li=temp;
		
	}
	
	public static class FireBall{
		int r;
		int c;
		int m;
		int s; 
		int d;
		public FireBall(int r, int c, int m, int s, int d) {
			this.r=r;
			this.c=c;
			this.m = m;
			this.s = s;
			this.d = d;
		}
		
	}
	public static class Info{
		ArrayList<FireBall> fbs;
		public Info(ArrayList<FireBall> fbs) {
			this.fbs=fbs;
		}
	}

}

board의 각 한 칸은 fireball 배열이다. 

 

K번 만큼 다음과 같은 과정을 반복한다:

Board를 초기화한다.

이동을 할 fireball을 담은 list를 순회하면서 조건에 맞게 움직여준다. (움직여줄 때, 1행과 N행, 1열과 N열은 이어져 있으므로, 이동 위치가 0 이하거나 N 을 넘어버리면 수를 더하거나 빼서 조정해준다.)

조건에 맞게 움직인다는 것은 board의 해당 위치에 fireball을 넣어버린다는 것을 의미한다.

마지막으로, 조정해주기 위해 board를 순회하면서 fireball이 2개 이상인 것에 대하여 질량, 속력 등을 계산하여 fireball을 새로 만든 뒤 탐색 list에 넣어주고, fireball이 1개인 칸은 그 그대로 탐색 list에 넣어준다. 

 

board와 탐색 list 2개의 자료구조를 쓰는 것이 중요한 시뮬레이션 문제였다.

 

다른 분들의 코드를 보니, 

board를 만들때 ArrayList<FireBall>[][] board 형태로 만들어 줄 수 있다.

또한 움직여줄때, 모듈러스 연산을 이용할 수 있다.

(fb.r+N+dr[fb,d]*(fb.s%N))%N 형태로 하면 조건대로 움직일 수 있다.

 

또한 board를 매번 refresh 할 필요 없이, makeBallList() 함수에서 다 이동 처리가 끝난 부분은 .clear(); 해주면 된다.

또한 탐색 list도 매번 clear할 필요 없이, board[i][j]에 있는 fireball이 1개일 경우 가만히 두고(move() 함수에서 고친 값이 그대로이므로), 2개 이상일 경우 그것들을 모두 list.remove(c) 해서 삭제한 뒤 새롭게 생성한 값을 다시 밀어넣어주면 된다.