백준 21610 : 마법사 상어와 비바라기

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

21610번: 마법사 상어와 비바라기

[ 문제풀이 ]

2021년 상반기 오후 삼성 공채 SW 역량 테스트 문제 중 하나인 마법사 상어와 비바라기 문제이다.

​오후 문제도 별다른 알고리즘은 필요 없이 주어진 조건대로 구현만 해주면 간단하게 해결할 수 있는 문제인 것 같다.

​삼성 기출문제를 접해봤다면 속력에 mod 연산을 적용하여 빠르게 계산하는 방법은 알 것이다.

​또한, 예시 그림을 보면 알겠지만 물복사버그 마법을 시전하여 바구니의 물양을 증가시킬 때 모든 영역에 마법을 시전한 다음 물을 증가시키는 순서로 해야 한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Cloud {
		int y, x;

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

	static int N, M;
	static int[][] A, temp;
	static boolean[][] visit;
	static Queue<Cloud> q;

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

	public static void main(String[] args) {
		try (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());
			A = new int[N][N];
			temp = new int[N][N];
			visit = new boolean[N][N];

			for (int i = 0; i < N; ++i) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; ++j) {
					A[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			q = new LinkedList<>();
			//초기 구름 생성
			q.offer(new Cloud(N - 1, 0));
			q.offer(new Cloud(N - 1, 1));
			q.offer(new Cloud(N - 2, 0));
			q.offer(new Cloud(N - 2, 1));

			for (int i = 0; i < M; ++i) {
				st = new StringTokenizer(br.readLine());
				int d = Integer.parseInt(st.nextToken()) - 1;
				int s = Integer.parseInt(st.nextToken()) % N;
				moveCloud(d, s);
				castWaterCopyMagic();
				createCloud();
				init();
			}
			bw.write(getWater() + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static void init() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				visit[i][j] = false;
				temp[i][j] = 0;
			}
		}
	}

	public static void moveCloud(int d, int s) {
		while (!q.isEmpty()) {
			Cloud cloud = q.poll();

			//mod 연산으로 빠르게 구해줌
			//다만, 음수가 나올 수 있기 때문에 N을 한 번 더해줌
			int ny = (cloud.y + dir[d][0] * s + N) % N;
			int nx = (cloud.x + dir[d][1] * s + N) % N;

			visit[ny][nx] = true;
			A[ny][nx]++;
		}
	}

	//모든 영역에 마법을 시전한 다음 물의 양을 증가시켜야함
	public static void castWaterCopyMagic() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (!visit[i][j]) continue;

				int bucketCnt = 0;
				for (int d = 1; d <= 8; d += 2) {
					int ny = i + dir[d][0];
					int nx = j + dir[d][1];

					if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
					if (A[ny][nx] == 0) continue;

					bucketCnt++;
				}
				temp[i][j] = bucketCnt;
			}
		}

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				A[i][j] += temp[i][j];
			}
		}
	}

	public static void createCloud() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (A[i][j] >= 2 && !visit[i][j]) {
					A[i][j] -= 2;
					q.offer(new Cloud(i, j));
				}
			}
		}
	}

	public static int getWater() {
		int sum = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				sum += A[i][j];
			}
		}
		return sum;
	}
}