자바 | 백준 | 21611 | 마법사 상어와 블리자드

Solution

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

public class Main {

	static int N, M;
	static int[][] map;
	static int[][] index;
	static int[] dx = { 0, -1, 1, 0, 0 };
	static int[] dy = { 0, 0, 0, -1, 1 }; // 북, 남, 서, 동
	static int[] dx2 = { 0, 1, 0, -1 };
	static int[] dy2 = { 1, 0, -1, 0 };
	static int[] d;
	static int[] s;
	static int[] bombs = new int[4];
	static Coor[] coors;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 1; j <= N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		index = new int[N + 1][N + 1];
		int idx = N * N;
		int dir = 0;
		int x = 1;
		int y = 0;
		coors = new Coor[N * N + 1];
		while (idx-- > 1) {
			int nx = x + dx2[dir];
			int ny = y + dy2[dir];

			if (!isIn(nx, ny) || index[nx][ny] != 0) {
				dir += 1;
				if (dir == 4) {
					dir = 0;
				}

				nx = x + dx2[dir];
				ny = y + dy2[dir];
			}
			index[nx][ny] = idx;
			coors[idx] = new Coor(nx, ny);
			x = nx;
			y = ny;
		}


		d = new int[M];
		s = new int[M];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			d[i] = Integer.parseInt(st.nextToken());
			s[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < M; i++) {
			func1(i);
			func2();
			while (func3()) {
				func2();
			}
			func4();
		}
		
		int sum = 0;
		for (int i = 1;i<=3;i++) {
			sum += bombs[i]*i;
		}
		System.out.println(sum);
	}

	static void func1(int command) {
		int x = (N + 1) / 2;
		int y = (N + 1) / 2;

		for (int i = 0; i < s[command]; i++) {
			x += dx[d[command]];
			y += dy[d[command]];

			if (isIn(x, y)) {
				map[x][y] = -1;
			}
		}
	}

	// 돌리기
	static void func2() {
		int[][] temp = new int[N + 1][N + 1];

		int empty = 0;
		for (int i = 1; i < N * N; i++) {
			if (map[coors[i].x][coors[i].y] == -1) {
				empty++;
			} else {
				temp[coors[i - empty].x][coors[i - empty].y] = map[coors[i].x][coors[i].y];
			}
		}

		for (int i = 0; i <= N; i++) {
			map[i] = temp[i].clone();
		}
	}

	static boolean func3() { // 4개 이상일 때 폭발
		int current = -1;
		int cnt = 0;
		boolean bombed = false;
		for (int i = 1; i < N * N; i++) {
			if (map[coors[i].x][coors[i].y] != current) {
				if (cnt >= 4) {
					for (; cnt > 0; cnt--) {
						bomb(map[coors[i - cnt].x][coors[i - cnt].y]);
						map[coors[i - cnt].x][coors[i - cnt].y] = -1;
					}
					bombed = true;
				}
				cnt = 1;
				current = map[coors[i].x][coors[i].y];
			} else {
				cnt++;
			}
		}
		return bombed;
	}

	static void func4() {
		int[][] temp = new int[N + 1][N + 1];
		int tempIndex = 1;

		int count = 0;
		int current = map[coors[1].x][coors[1].y];
		for (int i = 1; i < N * N; i++) {
			if (map[coors[i].x][coors[i].y] != current) {
				if (tempIndex >= N * N) {
					continue;
				}
				temp[coors[tempIndex].x][coors[tempIndex++].y] = count;
				temp[coors[tempIndex].x][coors[tempIndex++].y] = current;
				current = map[coors[i].x][coors[i].y];
				count = 1;
			} else {
				count++;
			}
		}

		for (int i = 0; i <= N; i++) {
			map[i] = temp[i].clone();
		}
	}

	static void bomb(int x) {
		bombs[x]++;
	}

	static boolean isIn(int x, int y) {
		return 1 <= x && x <= N && 1 <= y && y <= N;
	}

	static class Coor {
		int x;
		int y;

		Coor(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

 

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