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

문제 출처:https://www.acmicpc.net/problem/21610

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

1. 입력

첫째 줄에 N, M이 주어진다.

둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.

다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.

 

2. 출력

첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

 

3. 풀이

: 먼저 모든 구름이 주어진 방향으로 s칸 이동할 수 있도록 구름의 좌표를 list에 넣고 이동시켜준다.

: 이동을 마친 후 구름이 있는 자리마다 물의 양을 1씩 증가시켜준다.

: 물복사버그는 구름이 있는 자리를 순회하며 각각의 대각선 자리를 보고 0보다 큰 값을 가진 자리 수 만큼 물의 양을 증가시켜 준다.

: 전체 배열을 순회하며 물의 양이 2이상인 곳을 찾고 현재 구름이 있던 자리가 아니라면 -2 해주고 구름의 좌표로 추가한다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N, M;
	static int[][] map;
	static boolean[][] v;
	static int[] dr = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
	static int[] dc = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] crossR = { -1, -1, 1, 1 };
	static int[] crossC = { -1, 1, -1, 1 };

	static class Point {
		int r, c;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + "]";
		}

	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		ArrayList<Point> cloud = new ArrayList<>();
		cloud.add(new Point(N - 1, 0));
		cloud.add(new Point(N - 1, 1));
		cloud.add(new Point(N - 2, 0));
		cloud.add(new Point(N - 2, 1));
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int d = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			
			// 구름 이동시키기
			v = new boolean[N][N];
			for (int k = 0, size = cloud.size(); k < size; k++) {
				cloud.get(k).r = mod(cloud.get(k).r + dr[d]*s);
				cloud.get(k).c = mod(cloud.get(k).c + dc[d]*s);
				map[cloud.get(k).r][cloud.get(k).c]++;

			}

			// 구름이 있는 칸에 물 1씩 증가
			for (int j = 0, size = cloud.size(); j < size; j++) {
				Point cur = cloud.get(j);
				v[cur.r][cur.c] = true;
				int cnt = 0;
				// 물복사버그 마법 사용
				for (int k = 0; k < 4; k++) {
					int nr = cur.r + crossR[k];
					int nc = cur.c + crossC[k];
					if (nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == 0)
						continue;
					cnt++;
				}
				map[cur.r][cur.c] += cnt;
			}

			//
			cloud.clear();
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < N; k++) {
					if (!v[j][k] && map[j][k] >= 2) {
						map[j][k] -= 2;
						cloud.add(new Point(j, k));
					}
				}
			}
		}
		// 물의 양 카운팅
		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sum += map[i][j];
			}
		}
		System.out.println(sum);
	}
	private static int mod(int num) {
		while(num < 0) {
			num += N;
		}
		return num % N;
	}
}