백준 20056 마법사 상어와 파이어볼 - 삼성 SW 역량 테스트 기출

백준 20056 마법사 상어와 파이어볼  - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

20056번: 마법사 상어와 파이어볼

 

2. 문제 해결에 대한 아이디어

1. 이 문제는 꼼꼼히 보지 않으면, 안 되는 문제이다. 요구하는 조건이 많다.

2. 파이어볼은 8방향으로 움직이며, 격자를 벗어나게 되는 경우 N행 <->1행, N열 <-> 1열로 넘어갈 수 있다.

3. 파이어볼은 한 칸에 여러개가 있으므로, List <Ball>을 갖는 Tile 객체의 배열이 필요하다.

4. 파이어볼은 한 턴 당 움직이고나서 나눠진다. 따라서 움직인 이후를 기록할 배열이 필요하다.

5. 움직임이 끝나고나서 초기화를 잘해야 한다.

   . board[i][j].list에 copyBoard[i][j].list를 deepCopy 해야 한다.

   . 다음 턴에 재활용하기 위해 copyBoard[i][j].list를 clear 한다.

6. 속도는 N보다 클 수 있으므로, 다음 위치를 구하는 연산에서 속도 % N 하여 속도를 보정한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	static int[] dirY = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] dirX = { 0, 1, 1, 1, 0, -1, -1, -1 };
	static Tile[][] board;
	static Tile[][] copyBoard; // 이동을 기록할 보드
	static int N, M, K;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] nmk = br.readLine().split(" ");
		N = Integer.parseInt(nmk[0]);
		M = Integer.parseInt(nmk[1]);
		K = Integer.parseInt(nmk[2]);

		board = new Tile[N][N];
		copyBoard = new Tile[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = new Tile();
				copyBoard[i][j] = new Tile();

			}
		}

		for (int i = 0; i < M; i++) {
			String[] line = br.readLine().split(" ");
			int y = Integer.parseInt(line[0]) - 1;
			int x = Integer.parseInt(line[1]) - 1;
			int m = Integer.parseInt(line[2]);
			int s = Integer.parseInt(line[3]);
			int d = Integer.parseInt(line[4]);
			board[y][x].list.add(new Ball(y, x, m, d, s));
		}

		for (int k = 0; k < K; k++) {

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (board[i][j].list.isEmpty())
						continue;
					ballMove(board[i][j].list);

				}
			}
			reset();

			// 나누기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (board[i][j].list.size() < 2)
						continue;
					List<Ball> tempList = divide(i, j, board[i][j].list);
					board[i][j].list.clear();
					board[i][j].list.addAll(tempList);

				}
			}

		}

		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j].list.isEmpty())
					continue;
				for (int k = 0; k < board[i][j].list.size(); k++) {
					sum += board[i][j].list.get(k).m;
				}

			}
		}

		System.out.println(sum);

	}

	static void ballMove(List<Ball> list) {
		for (int i = 0; i < list.size(); i++) {
			Ball now = list.get(i);
			int y = now.y;
			int x = now.x;
			int dir = now.d;
			int speed = now.s;

			int yy = y + dirY[dir] * speed % N;
			int xx = x + dirX[dir] * speed % N;
			
			if (yy < 0) {
				yy = N + yy;
			} else if (yy >= N) {
				yy = yy - N;
			}

			if (xx < 0) {
				xx = N + xx;
			} else if (xx >= N) {
				xx = xx - N;
			}

			copyBoard[yy][xx].list.add(new Ball(yy, xx, now.m, now.d, now.s));
		}
	}

	static void reset() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j].list.clear();
				board[i][j].list.addAll(copyBoard[i][j].list);
				copyBoard[i][j].list.clear();
			}

		}
	}

	static List<Ball> divide(int y, int x, List<Ball> list) {
		Ball sum = new Ball(y, x, 0, 0, 0);
		int odd = 0;
		int even = 0;
		for (int i = 0; i < list.size(); i++) {
			Ball temp = list.get(i);
			sum.m += temp.m;
			sum.s += temp.s;
			if (temp.d % 2 == 0) {
				even++;
			} else {
				odd++;
			}
		}

		List<Ball> tempList = new ArrayList<>();

		if (sum.m < 5) {
			return tempList;
		}

		int nextM = sum.m / 5;
		int nextS = sum.s / (list.size());

		int startNum;
		if (even == list.size() || odd == list.size()) {
			startNum = 0;
		} else {
			startNum = 1;
		}

		for (int i = 0; i < 4; i++) {
			tempList.add(new Ball(y, x, nextM, startNum, nextS));
			startNum += 2;
		}

		return tempList;
	}

}

class Tile {
	List<Ball> list = new ArrayList<>();
}

class Ball {
	// 좌표 / 무게 / 방향 / 속력
	int y, x, m, d, s;

	public Ball() {

	}

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

}

 

4. 채점 결과

 

5. 느낀 점

1. 이 문제 또한 시험장에서 풀었던 문제로 시간이 부족해 다 풀지는 못 했었다.

2. 문제를 꼼꼼히 살펴보지 않았던 탓에 아래의 실수를 했다.

   . 합쳐진 후 나눠질 4개의 파이어볼의 방향을 결정하는 조건을 꼼꼼히 보지 못했다.

      . 합쳐질 파이어볼의 방향이 모두 홀수 혹은 짝수 일 때와 아닐 때로 나눠진다.

      . 합쳐질 파이어볼의 방향을 모두 더한 값이 홀수이거나 짝수인 것으로 나누는 잘못을 했다.

   . 파이어볼이 움직일 때, 격자를 벗어났을 때의 위치를 제대로 못 잡았다.

      . 파이어볼이 격자를 넘어가는 경우를 (-N, -N) ~ (N, N)으로만 생각했었다.

      . 하지만 이보다 격자의 크기 * (임의의 수) 만큼 벗어날 수 있으므로 % 을 하여 조정해야 했다.