BOJ - 20056 마법사 상어와 파이어볼

20056 마법사 상어와 파이어볼 : https://www.acmicpc.net/problem/20056

---

Problem

---

Solve

첫 번째 풀이에서 문제를 잘못이해해서 또 몇시간을 허비했다...

1번행과 N번 행까지 번호가 매겨져있고, 1번 열과 N번 열까지 연결되어있다는 조건을 지나쳤다..
그리고 2개 이상의 파이어볼이 있을때 파이어볼 방향의 합이 홀,짝일 때로 잘못 봤었다..

조건은 아래와 같다.

1. 모든 파이어볼이 자신의 방향 d와 속력 s칸 만큼 이동한다.
2. 파이어볼은 4개의 파이어볼로 나누어진다.
3. 이동 후 2개 이상의 파이어볼이 같은 칸에 있는 경우
   • 질량 : 질량의 합 /5
   • 속력 : 속력의 합 / 현재 합쳐진 파이어볼의 개수
   • 파이어볼의 방향이 모두 홀수이거나 짝수 일 경우 0,2,4,6이고 그렇지 않으면 1,3,5,7이다.
4. 질량이 0인 파이어 볼은 소멸된다.

이 문제 구현의 핵심은 List< Fire >[][] map으로 구성한 배열을 사용하는 것이라 생각한다.
map[i][j]에 있는 파이어볼을 이동시킬때 다음 좌표의 파이어볼 리스트에 저장하고 모든 파이어 볼을 이동시킨 후 각 좌표에 list의 크기가 2이상인 좌표의 리스트를 조건에 맞게 파이어볼을 생성하고 질량이 0인 파이어볼이 생성된다면 추가하지 않는 식으로 구현했다.

---

Code

public class 마법사상어와파이어볼 {
	static int N;
	static int M;
	static int K;
	static List<Fire>[][] map;

	static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		map = new List[N][N];

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

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			int r = Integer.parseInt(st.nextToken()) - 1;
			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());

			map[r][c].add(new Fire(m, d, s));
		}

		//K번 동안 파이어볼 이동
		while (K-- > 0) {
			move();
		}
        //남아있는 파이어볼 질량의 합
		int answer = check();

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static int check() {
		int sumM = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!map[i][j].isEmpty()) {
					for (Fire fire : map[i][j]) {
						sumM += fire.m;
					}
				}
			}
		}
		return sumM;
	}

	static void moveFire(int r, int c, Fire fire, List<Fire>[][] cloneMap) {
		int ny = r;
		int nx = c;
		for (int i = 1; i <= fire.s; i++) {
        	//각 처음과 마지막의 행과 열은 연결되어있다.
			ny = (ny + dy[fire.d]) % N;
			nx = (nx + dx[fire.d]) % N;


			if (ny < 0) {
				ny = N - 1;
			}
			if (nx < 0) {
				nx = N - 1;
			}
		}

		cloneMap[ny][nx].add(fire);
	}

	static void separateFire(int r, int c, List<Fire>[][] cloneMap) {
		int totalM = 0;
		int totalS = 0;
		int totalSize = cloneMap[r][c].size();

		int evenCount = 0;
		int oddCount = 0;
		for (Fire fire : cloneMap[r][c]) {
			totalM += fire.m;
			totalS += fire.s;

			if(fire.d % 2 ==0) evenCount++;
			else oddCount++;
		}

		cloneMap[r][c].clear();

		int m = totalM / 5;
		int s = totalS / totalSize;

		if (m == 0)
			return;

		//모든 파이어볼의 방향이 짝수거나 홀수여야하기 때문에 둘개의 카운터중 하나만 0이 아니어야 0,2,4,6 조건을 만족한다.
		if (evenCount == 0 || oddCount == 0) {
			for (int i = 0; i < 4; i++) {
				cloneMap[r][c].add(new Fire(m, 2 * i, s));
			}
		} else {
			for (int i = 0; i < 4; i++) {
				cloneMap[r][c].add(new Fire(m, 1 + 2 * i, s));
			}
		}
	}

	static void move() {
    	//이동한 파이어볼 저장
        //기존 배열에 있는 파이어볼 리스트에 영향을 주지 않기 위함.
		List<Fire>[][] cloneMap = cloneMap();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!map[i][j].isEmpty()) {
                	//해당 좌표의 파이어볼 리스트에 있는 파이어볼 이동
					int size = map[i][j].size();
					for (int f = 0; f < size; f++) {
						Fire fire = map[i][j].get(f);
						moveFire(i, j, fire, cloneMap);
					}
					map[i][j].clear();
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
            	//2개 이상의 파이어볼이 있는 곳의 파이어볼을 하나로 합치고 4개로 나눈다.
				if (cloneMap[i][j].size() >= 2) {
					separateFire(i, j, cloneMap);
				}
			}
		}

		map = cloneMap;
	}

	static List<Fire>[][] cloneMap() {
		List<Fire>[][] cloneMap = new List[N][N];

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

		return cloneMap;
	}

	static class Fire {
		int m;
		int d;
		int s;

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

---

Result

---

Reference