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

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

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

목표 : M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

 

문제 풀이 : 

map 배열 : 비바라기 크기가 N*N인 격자

visited 배열 : 구름의 위치

arr 배열 : 방향 d와 거리 s를 담은 이동명령 배열

dir 배열 : 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙

list : 비구름

Pair 클래스 : list를 쌍으로 받기 위한 클래스

 

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   1. 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   2. 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

1~5번 규칙대로 함수를 이용해 풀어주었습니다. 

이때, '3. 구름이 모두 사라진다'는 '4. 물복사버그 마법' 이후에 해주었습니다. 그 이유는 비구름의 위치를 알아야하기 때문입니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
class Pair{
	int r, c;
	public Pair(int r, int c) {
		this.r = r;
		this.c = c;
	}
}
class Solution {
	static int N, M;
	static int[][] map;
	static boolean[][] visited;
	static int[][] arr;
	static int[][] dir = { { 0, 0 }, { 0, -1 }, { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 },
			{ 1, -1 } };
	static ArrayList<Pair> list = new ArrayList(); //구름
	public static void main(String[] args) throws IOException {
		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][N];
		arr = new int[M][2];
		
		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());
			}
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine()," ");
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}//end of input
		
		//처음 구름 위치
		list.add(new Pair(N-2,0));
		list.add(new Pair(N-1,0));
		list.add(new Pair(N-2,1));
		list.add(new Pair(N-1,1));
		
		for (int i = 0; i < M; i++) {
			visited = new boolean[N][N];
			int d = arr[i][0];
			int s = arr[i][1];
			movecloud(d,s);
			rain();
			createcloud();
		}
		
		System.out.println(count());
		
	}
	//1. 모든 구름이 d 방향으로 s칸 이동한다.
	public static void movecloud(int d, int s) {
		for(Pair p : list) {
			int x = (p.r + N + dir[d][0] * s % N) % N;
			int y = (p.c + N + dir[d][1] * s % N) % N;
			
			visited[x][y] = true;
			//2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
			map[x][y] += 1;
			p.r = x;
			p.c = y;
			
		}
	}

	//4. 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
	public static void rain() {
		for(Pair p : list) {
			int count = 0, x = 0, y = 0;
		
			for(int i = 2; i<=8; i+=2) { 
				x = p.r + dir[i][0];
				y = p.c + dir[i][1];
				
				if(isInside(x,y) && map[x][y] > 0) {
					count++;
				}
			}
			map[p.r][p.c] += count;
			
		}
		//3. 구름이 모두 사라진다.
		list = new ArrayList();
	}
	//5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
	public static void createcloud() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				
				if(map[i][j] >= 2 && !visited[i][j]) {
					map[i][j] -=2;
					list.add(new Pair(i,j));
				}
			}
		}
	}
	
	//M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합
	public static int count() {
		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				count+=map[i][j];
			}
		}
		return count;
	}
	//배열의 범위를 넘어가지 않는지 확인
	public static boolean isInside(int x, int y) {
		return x>=0 && y>=0 && x<N && y<N;
	}
	
}