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

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

 

[ 문제 요약 ]

• N*N 격자에서 스킬 연습을 합니다. 각 칸에는 바구니가 있고 물을 무제한으로 저장할 수 있습니다.
• A[y][x]는 (y, x) 위치에 있는 바구니에 저장되어 있는 물의 양을 의미합니다.
• 격자의 가장 왼쪽 윗칸은 (1, 1)부터 시작합니다. 가장 오른쪽 아래 칸은 (N, N)입니다.
• 연습을 위해 1번 행과 N 번 행을 연결했고, 1번 열과 N 번 열도 연결했습니다.
• 즉 N 번 행의 아래는 1번 행이, 1번 행의 위에는 N 번 행이 있고, 1번 열의 왼쪽에는 N 번 열이, N 번 열의 오른쪽에는 1번 열이 있습니다.
• 스킬을 쓰면 (N, 1) (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생깁니다.
• 이제 구름에 M 번 이동 명령을 합니다.
• i 번째 이동 명령은 방향 di와 거리 si로 이뤄져 있고 방향은 현재칸 기준 8방향이 주어집니다.(1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙)
• 이동을 명령하면 다음이 순서대로 진행됩니다.

1. 모든 구름이 d 방향으로 s 칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1증가
3. 구름이 모두 사라짐
4. 2에서 물이 증가한 칸(y, x)들 하나하나에 물복사 마법을 사용한다. 물증 칸마다 그 칸의 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 현재 칸의 물 양을 증가시킨다. (내 주변 대각선에 3개 칸에 물이 있다면 현재 칸에 3증가)

• 이때는 이동과 다르게 경계를 넘어가는 대각선 칸은 연산에서 제외한다

1. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 그곳의 물 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니여야 한다.

• M 번의 이동이 끝난 후 바구니의 물의 양의 합을 출력합니다.

 

[ 테스트 케이스 설명 ]

5 4 // 지도의 크기(2<=50), 이동 횟수(1<=100)
0 0 1 0 2 // 초기 물의양이 제공됨
2 3 2 1 0
4 3 2 9 0
1 0 2 9 0
8 8 2 1 0
1 3 // 이동명령 방향(1<=8), 이동칸수(1<=50)가 순서대로 주어집니다.
3 4
8 1
4 8
이동이 모두 끝난 후 바구니의 물의 합 : 77

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

 

단순한 구현 문제입니다. 초기 구름을 세팅하고, 주어지는 이동 명령에 따라 구름을 이동한 후, 그곳의 물의 양을 추가합니다.

 

그 후 물을 복사하고, 이전 구름 장소를 제외한 구름 장소에 물이 2 이상이면 그곳에 구름을 세팅해 줍니다.

 

구름이 이동할 때, 맵을 초과하면 반대편으로 나타나도록 하기 위해 모듈러 연산을 사용합니다.

 

int xy[] = dxy[dir];
int ny = (y + (xy[0]*cnt)) % N;// 이동하는 만큼 곱하고, 그 결과를 모듈러 처리
int nx = (x + (xy[1]*cnt)) % N;
				
if(ny < 0)ny += N;// 음수인 경우 N을 더함
if(nx < 0)nx += N;

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
	
	static final int[][] dxy = {{},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},};// 대각선 인덱스 : 2,4,6,8
	static boolean[][] isCloud, isCloudDummy;
	static int[][] map;
	static int N, M;
	
	public static void main(String[] args)throws Exception{
		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];
		isCloud = new boolean[N][N];
		isCloudDummy = new boolean[N][N];
		
		for(int y=0; y<N; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=0; x<N; x++)
				map[y][x] = Integer.parseInt(st.nextToken());
		}
		
		isCloud[N-1][0] = isCloud[N-1][1] = isCloud[N-2][0] = isCloud[N-2][1] = true;
		
		while(M-->0)
		{
			st = new StringTokenizer(br.readLine());
			int d = Integer.parseInt(st.nextToken());// 이동명령 방향(1<=8)
			int k = Integer.parseInt(st.nextToken());// 이동칸수(1<=50)가 순서대로 주어집니다.
			
			moveCloud(d, k);// 구름 이동 및 이동 장소에 물의 양 1증가
			inc();// 물이 증가한 칸의 물복사
			makeCloud();// 처음 구름을 제외한 모든 장소에 물의 양이 2이상인 곳에 구름을 만들고, 그곳의 물의 양이 2줄어든다.
		}
		System.out.print(sum());
	}
	static void moveCloud(int dir, int cnt) {
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				if(!isCloud[y][x])// 구름이 아니면 제외
					continue;
				
				int xy[] = dxy[dir];
				int ny = (y + (xy[0]*cnt)) % N;
				int nx = (x + (xy[1]*cnt)) % N;
				
				if(ny < 0)ny += N;
				if(nx < 0)nx += N;
				
				isCloudDummy[ny][nx] = true;// 구름
				map[ny][nx] += 1;// 물 추가
			}
		}
		isCloud = isCloudDummy;
		
		isCloudDummy = new boolean[N][N];
	}
	static void makeCloud() {
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				if(!isCloud[y][x] && map[y][x] >=2)//구름이 아니였고, 물이 2이상이면, 구름이 됨
				{
					map[y][x] -= 2;
					isCloud[y][x] = true;
				}
				else
					isCloud[y][x] = false;
			}
		}
	}
	static void inc() {
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				if(!isCloud[y][x])// 구름이 아니였다면 제외
					continue;
				
				int cnt = 0;
				
				for(int i=2; i<=8; i+=2)
				{
					int ny = y + dxy[i][0];
					int nx = x + dxy[i][1];
					
					if(0<=ny && 0<=nx && ny<N && nx<N && 0 < map[ny][nx])
						++cnt;
				}
				
				map[y][x] += cnt;
			}
		}
	}
	static int sum() {
		int sum = 0;
		for(int y=0; y<N; y++)
			for(int x=0; x<N; x++)
				sum += map[y][x];
		return sum;
	}
}