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

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

 

[ 문제 요약 ]

• 크기가 N*N인 격자에 파이어볼 M 개를 발사했습니다. 가장 처음 파이어볼은 각자 위치에서 이동을 대기합니다.
• i 번 파이어볼의 위치는 (y, x) 질량은 mi, 속력은 si입니다. 좌표는 1부터 시작입니다.
• 1번 행은 N 번 행과 연결되어 있고, 1번 열은 N 번 열과 연결되어 있습니다.
• 파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 아래와 같습니다.

7 0 1
6   2
5 4 3

 

• 모든 파이어볼에게 이동을 명령하면 다음 일이 일어납니다.

1. 모든 파이어볼이 자신의 방향 d로 s 칸만큼 이동합니다(동일 칸에 여러 파이어볼 가능)
2. 이동이 모두 끝난 후 2개 이상의 파이어볼이 있는 칸에 아래 일이 일어납니다.
   1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐집니다.
   2. 파이어볼은 4개의 파이어볼로 나누어집니다.
   3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같습니다.
      1. 질량은 (합쳐진 파이어볼 질량의 합 / 5)입니다.
      2. 속력은 (합쳐진 파이어볼 속력의 합) / (합쳐진 파이어볼의 개수)입니다.
      3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 됩니다.
      4. 질량이 0인 파이어볼은 소멸되어 없어집니다.

• 이동 명령을 k 번 한 후 남아있는 파이어볼 질양의 합을 출력합니다.

 

[ 테스트 케이스 설명 ]

7 5 3 // 맵크기(4<=50), 초기 파이어볼 정보(0<=N^2), 이동횟수(1<=1000)
1 3 5 2 4 // y, x, 질량(1<=1000), 속력(1<=1000), 방향(0<=7)
2 3 5 2 6
5 2 9 1 7
6 2 1 3 5
4 4 2 4 2
남아있는 파이어볼 질양의 합 : 9

 

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

 

각 파이어볼들의 방향에 따라 이동한 후, 각 위치에서 파이어볼들을 합치고, 4개로 나눠 저장하는 단순 구현 문제입니다.

 

파이어볼들을 합친 후 나눌 때 같은 공간에 파이어볼이 2개 이상인지 확인하기 위해 2차원 큐배열 하나와, 일반 일차원 큐를 선언합니다.

 

처음 시작 시 일반 큐에 데이터를 담고, 이동 명령을 할 때 일반 큐 데이터를 꺼내 이동 방향으로 좌표를 갱신한 후 2차원 큐배열에 넣어 줍니다.(이렇게 해야 어느 좌표에 2개가 있는지 바로 확인할 수 있습니다.)

 

그 후 2차원 큐 배열을 돌며 같은 장소에 파이어볼이 2개 이상인 경우와 아닌 경우로 나눠 연산을 하고, 데이터를 일반 큐에 넣어 줍니다. 이 과정을 반복합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

class Main{
	
	static final int dxy[][] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
	static ArrayDeque<FireBall>[][] map;
	static ArrayDeque<FireBall> dummy;
	static int N, M, K;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 맵크기(4<=50)
		M = Integer.parseInt(st.nextToken());// 초기 파이어볼 정보(0<=N^2)
		K = Integer.parseInt(st.nextToken());// 이동횟수(1<=1000)
		map = new ArrayDeque[N][N];
		dummy = new ArrayDeque<>();
		
		for(int y=0; y<N; y++)
			for(int x=0; x<N; x++)
				map[y][x] = new ArrayDeque<>();
		
		while(M-->0)
		{
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			int w = Integer.parseInt(st.nextToken());// 질량(1<=1000)
			int c = Integer.parseInt(st.nextToken());// 속력(1<=1000)
			int d = Integer.parseInt(st.nextToken());// 방향(0<=7)
			
			dummy.add(new FireBall(y, x, w, c, d));
		}
		
		while(K-->0)
		{
			move();
			sumAndDiv();
		}
		
		System.out.print(print());
	}
	static void move() {
		while(!dummy.isEmpty())
		{
			FireBall f = dummy.poll();
			int ny = (f.y + (f.cnt*dxy[f.dir][0])) % N;
			int nx = (f.x + (f.cnt*dxy[f.dir][1])) % N;
			
			if(ny < 0) ny+=N;
			if(nx < 0) nx+=N;
			
			f.y = ny;
			f.x = nx;
			
			map[ny][nx].add(f);
		}
	}
	static void sumAndDiv() {
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				ArrayDeque<FireBall> q = map[y][x];
				int size = q.size();
				if(size < 2)
				{
					if(!q.isEmpty())
						dummy.add(q.poll());
					continue;
				}
				
				int weightSum = 0;
				int cntSum = 0;
				int odd = 0;
				
				while(!q.isEmpty())
				{
					FireBall f = q.poll();
					weightSum += f.weight;
					cntSum += f.cnt;
					if(f.dir % 2 != 0)
						odd++;
				}
				
				weightSum /= 5;
				cntSum /= size;
				
				if(weightSum <= 0)// 질량이 0이면 스킵
					continue;
				// 모두 홀수나 짝수인 경우 방향은 0부터 시작해서 짝수, 아니면 1부터 시작해서 홀수
				int d = (odd == size) || (odd == 0) ? 0 : 1;
				
				for(int i=d; i<=7; i+= 2)
					dummy.add(new FireBall(y, x, weightSum, cntSum, i));
			}
		}
	}
	static int print() {
		int sum = 0;
		
		while(!dummy.isEmpty())
			sum += dummy.poll().weight;

		return sum;
	}
	static class FireBall{
		int y, x, weight, cnt, dir;
		FireBall(int y, int x, int w, int c, int d){
			this.y=y;
			this.x=x;
			this.weight = w;
			this.cnt = c;
			this.dir = d;
		}
	}
}

 

[ 테스트 케이스 ]

4 1 1
1 4 7 4 7
답: 7

5 3 5
4 4 10 7 1
1 4 5 2 0
3 2 2 10 6
답 : 17