백준 20056 : 마법사 상어와 파이어볼

문제 링크

---

접근 방법

시뮬레이션 문제이기 때문에 문제에서 어떤 데이터가 필요한지 먼저 분석했다.

 

파이어볼이 이동한 후 위치에 대한 파이어볼 정보를 파악해야 했다 .

→  map[][]에 파이어볼의 정보를 저장

 

한 위치에 여러 개의 파이어볼이 존재할 수 있다.

→  map[][]을 리스트로 보관해야 할까? (하나로 합쳐서 저장할 수 있다)

 

 

파이어볼이 나누어지는 과정의 단순화 

• 질량 : 파이어볼들의 질량 합에서 상수인 5로 나누기 때문에 누적해서 저장하면 된다.
• 속력 : 파이어볼들의 속력 합에서 개수로 나누기 때문에 누적해서 저장하고 개수를 따로 세어주면 된다.
• 방향 : 모두 홀수이거나 모두 짝수인 경우를 생각해야 하는데 Boolean 2개로 처리하자.

 

따라서 파이어볼 정보(m, s, d, cnt, odd, even)를 담는 Ball 클래스를 선언하였다. 

m, s, d는 입력값이며 cnt는 몇 개의 파이어볼이 합쳐졌는지를 저장한다. odd와 even은 홀수나 짝수가 있다면 true로 만들어서 둘 중 하나라도 false가 있다면 모두 홀수이거나 모두 짝수인 경우라고 판단하였다.

 

Ball map[][]에는 해당 위치에 존재하는 파이어볼의 정보를 저장하였다.

 

파이어볼이 나누어질 때 d는 모두 짝수이거나 모두 홀수라면 0으로 설정하고

아니라면 1로 설정한 후 d부터 +2를 한 방향으로 파이어볼을 이동시켰다.

---

삽질했던 부분

1. 파이어 볼 이동의 동시성

이미 이동한 파이어볼과 이동할 파이어볼을 따로 생각해야 했다.

파이어볼을 하나로 합치는 방식으로 구현했기 때문에 A 파이어볼을 B 파이어볼 위치로 이동시키는데 B 파이어볼이 아직 이동하기 전이라면 논리적 오류가 발생한다.

따라서 임시맵을 만들어서 단계를 나누어 주었다.

 

2. 짝수/홀수 판단의 초기화

Boolean 2개로 모두 짝수인지 모두 홀수인지 검사하도록 만들었는데

초기 방향에 대해서는 체크를 해주지 않아서 디버깅을 꽤 오래 했다... 8ㅅ8

간단하게 생성자에 추가하여 구현하였다.

---

후기

삼성 역량 테스트 오전 문제였는데 삽질을 많이 해서인지 내가 본 오후 시험보다 어렵게 느껴졌다. 

구현력을 키우기 위한 좋은 문제라고 생각했다.

 

아직 푼 사람이 많이 없긴 하지만 시간이 제일 짧아서 뿌듯했다 ㅎ_ㅎ

코드

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

/*
 *  20056. 마법사 상어와 파이어볼
 *  https://www.acmicpc.net/problem/20056
 */
public class Main {
	static int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
	static Ball map[][], next[][];
	static int ans, N;

	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());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		map = new Ball[N][N];
		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] = new Ball(m, s, d);
		}
		for (int i = 0; i < K; i++)
			move();
		sol();
		System.out.println(ans);
	}

	static void move() {
		next = new Ball[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == null)
					continue;
				// 해당 위치에 파이어볼이 존재한다면 정보를 확인한다.
				int move = 1; // 이동할 파이어볼의 개수
				Ball b = map[i][j];
				// 여러개의 파이어 볼이 있다면 조건에 맞게 하나로 만들고 move만 4로 해준다.
				if (b.cnt > 1) {
					b.d = (!b.even || !b.odd) ? 0 : 1;
					b.m /= 5;
					b.s /= b.cnt;
					move = 4;
					if (b.m == 0)
						continue;
				}
				// 파이어볼의 방향으로 이동시켜준다.
				// 이때 move가 4라면 d부터 돌면서 4번 이동시킨다.
				for (int k = 0; k < move; k++, b.d += 2) {
					int nr = (i + dr[b.d] * b.s + (N * b.s)) % N;
					int nc = (j + dc[b.d] * b.s + (N * b.s)) % N;
					// 새로운 위치에 파이어볼이 없다면 그냥 대입하고
					if (next[nr][nc] == null)
						next[nr][nc] = new Ball(b.m, b.s, b.d);
					// 새로운 위치에 파이어볼이 존재한다면 합쳐준다.
					else {
						Ball b2 = next[nr][nc];
						b2.m += b.m;
						b2.s += b.s;
						b2.cnt++;
						if (b.d % 2 == 0)
							b2.even = true;
						else
							b2.odd = true;
					}
				}
			}
		}
		for (int i = 0; i < N; i++)
			map[i] = next[i].clone();
	}

	// 남은 파이어볼들의 질량을 더해준다.
	static void sol() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				Ball b = map[i][j];
				if (b == null)
					continue;
				if (b.cnt == 1)
					ans += b.m;
				else // 원래는 이동이 끝나면 바로 나누어지기 때문에 나눈 후의 질량을 더해준다.
					ans += b.m / 5 * 4;
			}
		}
	}

	static class Ball {
		int m, s, d, cnt;
		boolean odd, even;

		public Ball(int m, int s, int d) {
			this.m = m;
			this.s = s;
			this.d = d;
			this.cnt = 1;
			if (this.d % 2 == 0)
				even = true;
			else
				odd = true;
		}
	}
}