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

문제 설명

• 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

	moduler연산이 필요하단 뜻입니다.

• 파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.

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

• 마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

	주어진 조건대로 구현을 진행해야 합니다.

접근법

• 모든 파이어볼이 다 움직이고 나서 분할되기 때문에 동일한 배열탐색에서 한번에 처리하면 안됩니다.
  • 움직임을 구현하는 2중for문을 다 돌고난 뒤 분할을 구현하는 2중for문을 동작시켜야 합니다.

pseudocode

2차원 배열 board가 list를 담고 있음.
list에는 fireball 객체가 들어감.
board = [[list()],[list(fball1,fball2)],
		[list(fball3)],[list()]] 

for(K번){
	move();
    split();
}
move(){
	for(board전체를 탐색하면서){
    	if(해당 칸의 list가 비었으면) continue;
        for(해당 칸의 list 크기만큼){
        	if(이번턴에 아직 안움직인 파이어볼이면){
                f = 해당 칸의 list에서 pollFirst();
                nx = (현재row + (방향 * 속도))%N;
                ny = (현재col + (방향 * 속도))%N;
			}
        }
        board[nx][ny]에 f를 이동        
    }
}
split(){
	for(board전체를 탐색하면서){
    	if(해당 칸의 list가 비었으면)continue;
        if(해당 칸에 파이어볼이 하나만 있으면){
        	다음턴에 움직일 수 있게 can_move true로 설정
        }else{ // 해당 칸에 파이어볼이 둘 이상이면
        	질량,속도,방향을 모두 합침.
            if(모든 d가 홀수거나 모든 d가 짝수면){
            	질량을 /5만큼, 속도를 /합친개수 만큼 가진 0,2,4,6방향의 파이어볼 4개 생성
            }else{
            	질량을 /5만큼, 속도를 /합친개수 만큼 가진 1,3,5,7방향의 파이어볼 4개 생성   
            }
        }
    }
}

정답

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

public class Main {
	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) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int K = sc.nextInt();
		Deque<fireball>[][] board = new Deque[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = new LinkedList<fireball>();
			}
		}
		// 최초 M개의 파이어볼을 생성합니다.
		for (int i = 0; i < M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int m = sc.nextInt();
			int s = sc.nextInt();
			int d = sc.nextInt();
			board[x - 1][y - 1].addLast(new fireball(x - 1, y - 1, m, s, d, true));

		}

		// K번 움직이고 분열합니다.
		for (int k = 0; k < K; k++) {
			move(N, board);
			split(N, board);
		}

		// 최종 점수를 계산합니다.
		int score = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j].size() == 0)
					continue;
				int size = board[i][j].size();
				for (int t = 0; t < size; t++) {
					fireball val = board[i][j].poll();
					score += val.m;
				}
			}
		}
		System.out.println(score);

	}

	public static void split(int N, Deque<fireball> board[][]) {
		// move 후 모든 board칸에 대해 검사를 진행합니다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j].size() == 0)
					continue; // 파이어볼이 없는 칸은 지나갑니다.
				if (board[i][j].size() == 1) { // 파이어볼이 하나만 있는 칸은 split하지 않고 다음번에 움직일 수 있게 can_move만 변경해 줍니다.
					fireball f = board[i][j].pollFirst();
					f.can_move = true;
					board[i][j].addLast(f);
				} else {

					int sumM = 0;
					int sumS = 0;
					int sumD = 0;
					int oddEven = board[i][j].peekFirst().d;
					boolean token = false;
					int size = board[i][j].size();
					for (int l = 0; l < size; l++) {
						fireball f = board[i][j].pollFirst();
						sumM += f.m;
						sumS += f.s;
						sumD += f.d;
						if (!token && f.d % 2 != oddEven % 2) { // 모든 d의 합이 짝수면 될 거라 생각했는데 아니였습니다(반례 - 1+1+2 = 4로 짝수지만 모든 수가 홀수 or 짝수 X)
							token = true;
						}
					}
					if (sumM / 5 == 0) {
						// 소멸
					} else if (!token) { // 모든 d가 홀수거나 짝수면
						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 0, true));
						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 2, true));
						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 4, true));
						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 6, true));
					} else {
						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 1, true));
						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 3, true));
						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 5, true));
						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 7, true));
					}
				}

			}
		}

	}

	public static void move(int N, Deque<fireball> board[][]) {
		// board에 있는 모든 fireball을 움직입니다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j].size() == 0)
					continue; // fireball이 없는 칸은 패스합니다.
				int size = board[i][j].size();
				for (int t = 0; t < size; t++) { // poll로
					if (board[i][j].peekFirst().can_move) { // 움직일 수 있으면(이미 어디선가 움직여서 온 fireball이 아니라는 의미입니다)
						fireball f = board[i][j].pollFirst();
						// 음수 모듈러 연산방법을 잘 모르겠습니다.(아래는 임시방편 코드)
						int nx = (f.r + dx[f.d] * f.s >= 0) ? (f.r + dx[f.d] * f.s) % N
								: (N * N * N * N * N + (f.r + dx[f.d] * f.s)) % N;
						int ny = (f.c + dy[f.d] * f.s >= 0) ? (f.c + dy[f.d] * f.s) % N
								: (N * N * N * N * N + (f.c + dy[f.d] * f.s)) % N;
						// 방향으로 속도만큼 이동 후 해당 위치로 불꽃을 옮깁니다.
						f.r = nx;
						f.c = ny;
						f.can_move = false; // 한번 움직였기 때문에 이번턴에는 더 이상 움직일 수 없습니다.
						board[nx][ny].addLast(f);
					}

				}
			}
		}
	}

	static class fireball {
		int r;
		int c;
		int m;
		int s;
		int d;
		boolean can_move;

		public fireball(int r, int c, int m, int s, int d, boolean can_move) {
			super();
			this.r = r;
			this.c = c;
			this.m = m;
			this.s = s;
			this.d = d;
			this.can_move = can_move;
		}

		@Override
		public String toString() {
			return "fireball [r=" + r + ", c=" + c + ", m=" + m + ", s=" + s + ", d=" + d + ", can_move=" + can_move
					+ "]";
		}

	}

}

기타

유의사항

• list에서 poll을 할 때 반복문으로 list.size()를 주면 안됩니다.
  • poll을 하면 list의 크기가 변하기 때문입니다.

// 잘못된 예시
for(int i = 0; i < list.size(); i++){
	val = list.poll();
}
// 올바른 방법
size = list.size()
for(int i = 0; i < size; i++){
	val = list.poll();
}

• 음수 모듈러연산 방법

  • 속력c를 c%n을 하면 최대 2*n의 범위 내에서 계산이 가능합니다.
    • (A*B)%C == (A*(B%C))%C
  • for문으로 한칸씩 움직이면서 n이 0이되면 다시 n을 채워주는 방법도 있다.

• 2차원 배열에 list나 queue와 같은 자료구조로 담는 게 좋은 방법일까? 메모리나 속도 측면에서 더 좋은 방법이 없을까?

  • 똑같이 2차원 배열에 list나 queue를 사용한 문제: 나무 재테크