[백준 20056] 마법사 상어와 파이어스톰 (JAVA)

🔰 문제

백준 20056번: 마법사 상어와 파이어스톰

💡 접근방식

미생물 격리 문제 때와 비슷하게

객체 리스트를 관리하는 ArrayList와 객체들이 이동 후 map에 배치하기 위해 2차원 배열 map을 설정하였다.

파이어볼 객체가 있다고 하면

ArrayList<FireBall> list;
ArrayList<FireBall> map[][];

2가지를 만들어서

파이어볼 객체들 list에 저장 -> list의 파이어볼들 이동(r, c 갱신) -> 이동한 파이어볼들 map에 배치 -> map에 배치된 파이어볼들 상태 보고 한 공간에 2개 이상의 파이어볼 있으면 쪼개기 -> 전부 처리한 뒤에 list에 파이어볼 담기

흐름으로 하는 문제였다.
ArrayList를 2차원 배열로 사용하는 것이 신기했던 문제다.

💦 풀면서 실수, 놓친 점

ArrayList 2차원 배열 선언 및 할당

ArrayList<FireBall> map = new ArrayList[N][N];
for(int i=0;i<N;i++){
	for(int j=0;j<N;j++){
    	map[i][j] = new ArrayList<FireBall>();
    }
}

문제 잘못 이해

한 칸에 여러개의 파이어볼이 있으면 4개로 나뉜다고 하였다. 나는 이것을 현재 칸 기준으로 (0,2,4,6) or (1,3,5,7) 방향으로 퍼진다고 착각하였다.
이거때문에 한참 삽질했다.. 문제를 잘 읽자!!!

파이어볼 이동식 구현

1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
이 부분을 구현할 때 잘못 구현하여 index out of error 발생

//파이어볼 이동

//기존(index out of error 발생)
cur.r = (cur.r + dx[cur.d] * cur.s + N) % N;
cur.c = (cur.c + dy[cur.d] * cur.s + N) % N;

//정답
cur.r = (cur.r + N + dx[cur.d] * (cur.s % N)) % N;
cur.c = (cur.c + N + dy[cur.d] * (cur.s % N)) % N;

잘못된 기존 코드를 사용할 경우 속도의 값(cur.s)가 매우 크고 x, y의 이동량(dx, dy)가 음수일 경우 cur.r 값이 음수가 될 수 있다.

위 식에서 cur.r = 0, dx = -1, cur.s = 7 N = 4 라고 가정하고 계산을 해보면 다음과 같이 잘못된 기존 식은 음수가 나온다.

System.out.println((0 + (-1) * 7 + 4) % 4); // -3
System.out.println((0 + 4 + (-1) * (7 % 4)) % 4); // 1

방향이 전부 홀인지 짝인지 구현

이건 실수한 것은 아니고, 참고한 풀이의 구현 방식이 더 간단한 것 같아 숙지해두면 좋을 것 같다.

boolean even = 첫번째 요소 %2==0?true : false;
boolean odd = 첫번째 요소 %2 == 1? true : false;

모든 요소 반복
	even = even & 현재 요소 %2==0?true:false;
    odd = odd & 현재 요소 %2==1?true:false;
반복 끝난 뒤에 
even || odd 일 경우, 전부 짝수이거나 전부 홀수 인 것이고
even==false && odd==false이면 짝, 홀 섞여 있는 것이다.

🕑 소요시간

70분

💻 풀이

import java.io.*;
import java.util.*;

public class Main_20056 {
	static class FireBall {
		int r, c, m, s, 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;
		}
	}

	static int N, M, K;
	static int res;
	static ArrayList<FireBall> map[][];
	static List<FireBall> list;
	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 Exception {
		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()); // 이동 명령 횟수
		map = new ArrayList[N][N]; // 파이어볼들 저장하는 격자

		for (int i = 0; i < N; i++) { // 격자 초기화
			for (int j = 0; j < N; j++) {
				map[i][j] = new ArrayList<FireBall>();
			}
		}
		list = new ArrayList<>(); // 파이어볼 리스트

		// FireBall 정보 입력받기
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()) - 1; // (1,1)부터 시작하는 것을 (0,0) 시작으로 바꿈
			int c = Integer.parseInt(st.nextToken()) - 1;
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			list.add(new FireBall(r, c, m, s, d));
		}

		simulation(); // 시뮬레이션 시작

		res = getResult(); // 남아있는 파이어볼 질량 합 구하기
		System.out.println(res);
	}

	private static int getResult() {
		int sum = 0;
		for (int i = 0; i < list.size(); i++) {
			sum += list.get(i).m;
		}
		return sum;

	}

	private static void simulation() {
		for (int time = 0; time < K; time++) { // K번동안 명령
			// 1. 파이어볼 이동
			for (int i = 0; i < list.size(); i++) {
				FireBall cur = list.get(i);
				// r, c 이동
				cur.r = (cur.r + N + dx[cur.d] * (cur.s % N)) % N;
				cur.c = (cur.c + N + dy[cur.d] * (cur.s % N)) % N;

				map[cur.r][cur.c].add(cur); // 이동후 map에 배치

			}

			// 2. 이동끝난 후 2개 이상의 파이어볼 있는 칸 체크
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j].size() > 1) {
						divide4(i, j);
					}
				}
			}

			// map에 배치한거 list에 담기
			list.clear();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j].size() != 0) {
						for (int k = 0; k < map[i][j].size(); k++) {
							FireBall cur = map[i][j].get(k);
							list.add(cur);
						}
					}
				}
			}
			// map 내용들 list에 다 담았으면, 다음 턴을 위해 map clear
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j].size() > 0)
						map[i][j].clear();
				}
			}
		}
	}

	private static void divide4(int x, int y) { // 4방향으로 나눠지기
		int sumM = 0, sumS = 0; // 질량합, 속력합
		boolean flag = true; // 방향 전부 홀,짝이면 true, 아니면 false

		for (int i = 0; i < map[x][y].size(); i++) {
			FireBall cur = map[x][y].get(i);
			sumM += cur.m;
			sumS += cur.s;
			if (i != map[x][y].size() - 1) {
				FireBall next = map[x][y].get(i + 1);
				if (cur.d % 2 != next.d % 2) // 홀, 짝 섞여있을 경우 flag=false
					flag = false;
			}
		}

		int newM = 0, newS = 0;
		newM = sumM / 5;
		newS = sumS / map[x][y].size();

		map[x][y].clear();
		setMap(newM, newS, flag, x, y);

	}

	private static void setMap(int newM, int newS, boolean flag, int x, int y) {
		if (newM != 0) { // 파이어볼 질량 0 아닐때만 살아남으므로
			if (flag) {
				for (int i = 0; i < 4; i++) {
					FireBall newFireBall = new FireBall(x, y, newM, newS, 2 * i);
					map[x][y].add(newFireBall);
				}
			} else {
				for (int i = 0; i < 4; i++) {
					FireBall newFireBall = new FireBall(x, y, newM, newS, 2 * i + 1);
					map[x][y].add(newFireBall);
				}
			}
		}
	}

}

🌟 비슷한 유형의 문제들

❗ 풀어보면 좋은 문제들

참고
[Java][백준 20056][시뮬레이션][삼성SW 역량 테스트] 마법사 상어와 파이어볼