[java] 백준(BOJ) - 마법사 상어와 파이어볼

문제

백준-마법사 상어와 파이어볼
파이어볼이 명령에 따라 K번 이동 한 후 남아있는 파이어볼 질량의 합을 구하는 문제

• 제한 사항
  맵의 크기 N : 4 ≤ N ≤ 50
  초기 파이어볼 개수 M : 0 ≤ M ≤ N2
  명령의 수 K : 1 ≤ K ≤ 1,000
  각 파이어볼의 질량 mi : 1 ≤ mi ≤ 1,000
  각 파이어볼의 속력 si : 1 ≤ si ≤ 1,000
  각 파이어볼의 방향 di : 0 ≤ di ≤ 7

풀이

시뮬 특징 그대로 시키는 대로 하면 된다
다만, N = 3인 맵의 [0, 0] 위치에서 2방향(우측)으로 5칸 움직인다고 하면
y값이 [0, 1, 2, 0, 1] 이렇게 움직여야한다 (행도 마찬가지)

시행착오 : 시간 소모 및 틀렸습니다

어레이리스트와 스택2개를 이용해서 풀이를 해봤다
대략적으로 설명하자면

1. 처음 파이어볼을 리스트(balls)에 넣는다
2. 리스트(balls)의 원소들을 순회하면서 다음 이동경로로 x,y를 바꿔준다
3. 리스트를 정렬한다(x,y 기준으로)
4. 리스트를 순환하면서 스택(tmp)와 다른 스택(cnt)에 넣는다
   (tmp는 ball을 담고, cnt는 ball의 방향에 따른 홀수, 짝수를 저장함)
   4-1. 이때 기존 스택(tmp)의 peek값과 x,y가 같으면 질량과 속도를 더해준다
   4-2. 4-1.에 이어, cnt에 현재 방향이 홀수면 홀수 증가, 짝수면 짝수 증가
5. tmp와 cnt를 같이 뽑으면서 balls에 추가한다
   5-1. cnt의 홀수+cnt의 짝수 > 1이면 2개 이상의 ball이 모인것이므로 tmp에서 뽑은 ball의 질량과 속력을 계산해서 원래 리스트(balls)에 4개를 추가한다
   5-2. 아닌경우 그냥 그대로 리스트(balls)에 추가

후.. 틀렸습니다도 초반에 조금 0%에서 떴다

< 내가 생각하는 원인 >

1. 다음 위치의 계산을 잘못함
   nx, ny를 구할 때 0보다 작으면 N을 더해주고, N보다 크면 N을 뺐다
   N = 50 이고 [0,0]위치에서 1000의 속도로 움직이면 [950, 0] 이렇게 나왔다
   리스트를 사용하니까 딱히 맵에 제약을 두지않았는데, 디버깅하다가 알았다

2. 입력값 미스
   나는 0부터 시작한다고 생각하고 코드를 짰다
   근데 문제 입력은 1이 인덱스의 시작값이다
   ㅠㅠ바보

3. 문제 이해 실수
   처음에 파이어볼이 4개로 갈라진다는게, 해당 방향의 위치로 나눠진다는 줄 알았다
   그런데 지금위치에 4개가 다른방향으로 분열되는 거였다
   다음차례의 이동에서 갈라진 파이어볼이 방향따라 제 갈길을 가는거였다

다 수정하고 제출했는데 정답이었지만, 반복해서 사용하는 스택2개 탓에 속도는 오늘시작하면 내일끝날 느낌이었다

그래서 ArrayList<Ball>[][][]로 수정했다
[x][y][flag]로 해서 몇번째 이동인지에 따라 flag를 교체하면서 사용했다
방법은 그대로 따라하면 되는거라서 생략 ~~

소스코드

(시뮬문제는 문제조건을 복사해서 주석달고 그~대로 써서 소스가 좀 길다)

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

public class Main {

	private static int N, M, K;
	static int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		ArrayList<Ball>[][][] balls = new ArrayList[N][N][2];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < 2; k++) {
					balls[i][j][k] = new ArrayList<>();
				}
			}
		}

		int x, y, m, s, d;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken()) - 1;
			y = Integer.parseInt(st.nextToken()) - 1;
			m = Integer.parseInt(st.nextToken());
			s = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());
			balls[x][y][0].add(new Ball(m, s, d));
		}

		for (int i = 0; i < K; i++) {
//			1.모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
			int flag = i % 2;
			int next = flag == 0 ? 1 : 0;
			for (int r = 0; r < N; r++) {
				for (int c = 0; c < N; c++) {
					while (!balls[r][c][flag].isEmpty()) {
						Ball curr = balls[r][c][flag].remove(0);
						int nx = r + dx[curr.d] * (curr.s % N);
						int ny = c + dy[curr.d] * (curr.s % N);
						nx = checkBoundary(nx);
						ny = checkBoundary(ny);
						balls[nx][ny][next].add(new Ball(curr.m, curr.s, curr.d));
					}
				}
			}

//			이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
//			2.이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
			for (int r = 0; r < N; r++) {
				for (int c = 0; c < N; c++) {
//			2-1.같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
//			2-2.파이어볼은 4개의 파이어볼로 나누어진다.
//			2-3-1.질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
//			2-3-2.속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
					if (balls[r][c][next].size() > 1) {
						int ms = 0;
						int ss = 0;
						int v[] = new int[2];
						while (!balls[r][c][next].isEmpty()) {
							Ball curr = balls[r][c][next].remove(0);
							if (curr.d % 2 == 0)
								v[0]++;
							else
								v[1]++;
							ms += curr.m;
							ss += curr.s;
						}
						ms /= 5;
//			2-4.질량이 0인 파이어볼은 소멸되어 없어진다.
						if (ms == 0)
							continue;
						int size = v[0] + v[1];
						ss /= size;
//			2-3-3.합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
						int start = v[0] == 0 || v[1] == 0 ? 0 : 1;
						for (int k = start; k < 8; k += 2) {
							balls[r][c][next].add(new Ball(ms, ss, k));
						}
					}
				}
			}
		}
		// 마지막
		int total = 0;
		for (int i = 0; i < balls.length; i++) {
			for (int j = 0; j < balls.length; j++) {
				for (int k = 0; k < balls[i][j][K % 2].size(); k++) {
					total += balls[i][j][K % 2].get(k).m;
				}
			}
		}
		System.out.println(total);
	}

	private static int checkBoundary(int i) {
		if (i < 0)
			i += N;
		if (i >= N)
			i -= N;
		return i;
	}
}

class Ball {
	int m;
	int s;
	int d;

	public Ball(int m, int s, int d) {
		super();
		this.m = m;
		this.s = s;
		this.d = d;
	}
}