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

1. 문제 링크

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

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

 

2. 문제 요약

# 초기 비구름 생성: (N, 1), (N, 2), (N-1, 1), (N-1, 2) 명령대로 아래 순서 진행
1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 마법 시전
   - 2번에서 구름이 존재한 곳에서 대작선 거리 1인 칸에 있는 수만큼 증가 + 1
   - 여기서는 경계 넘어가면 안쳐줌
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다.
    이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

3. 아이디어 정리

• 초기화 비구름 생성: (N, 1), (N, 2), (N-1, 1), (N-1, 2) 

명령 순서대로 아래 진행

1. 구름 이동: 모든 구름이 di 방향으로 si칸 이동한다.
2. 바구니 물 증가: 1위치에 +1 증가한다.
3. 마법 시전: 구름 위치 대각선 위치에 물이 있는 수만큼 + 1
4. 다음 구름 생성: 바구니에 저장된 물의 양이 2 이상인 모든 칸& 3에서 구름 제거 x에 구름이 생기고 2 줄어든다.
5. 다음 구름을 현재 구름으로 변경

 

4. 문제 풀이

4-1. 내 풀이

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

public class Main{
	static int result, n, m = 0 ;
	static int[][] arr, cloud;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	//  ←, ↖, ↑, ↗, →, ↘, ↓, ↙
	static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
	static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
	
	static int[] dx2 = {-1, -1, 1, 1};
	static int[] dy2 = {-1, 1, 1, -1};
	
public static void main(String[] args) throws Exception {
    	
    	st = new StringTokenizer(br.readLine());
    	n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
         
        arr = new int[n][n];      // 바구니 물의 양 저장 
        cloud = new int[n][n];    // 구름 존재 저장 
        
        // 구름 초기화 
        cloud[n - 1][0] = 1;
        cloud[n - 1][1] = 1;
        cloud[n - 2][0] = 1;
        cloud[n - 2][1] = 1;
    	 // 바구니 물의 양 
    	 for (int i = 0; i < n; i++) {
    		 st = new StringTokenizer(br.readLine());
    		 for (int j = 0; j < n; j++) {
    			 arr[i][j] = Integer.parseInt(st.nextToken());
    		 }
    	 }
    	 // m번의 이동 
    	 for(int i = 0; i < m; i++) {
    		 st = new StringTokenizer(br.readLine());
    	     int d = Integer.parseInt(st.nextToken());
    	     int s = Integer.parseInt(st.nextToken()) % n;
    	     
    	     // 1. 모든 구름이 이동 
    	     cloud = move(d - 1, s);
    	     // 2. 각 구름에 비가 내려 바구니 + 1
    	    rain();
    	     // 3. 구름 사라짐 (pass) 
    	     // 4. 구름있는 칸 마법 시전 
    	      // - 대각선 방향 1인 칸 바구니 물 양 증가. 칸 넘는 것은 취급 안함
    	    magic();
    	     // 5. 물 2이상인 칸&3에서 구름이 없는 경우 =>  구름 생기고, 바구니 -2
    	    cloud = make_cloud();
    	     
    	   
    	 }
    	 // 결과 
 	    for(int x = 0; x < n; x++) {
	    	 for(int y = 0; y < n; y++) {
	    		 result += arr[x][y];
	    		 }
	    	 }
    	 
       bw.append(Integer.toString(result));
       bw.flush();    
    }
	
	public static int[][] move(int d, int s){
	     int[][] ncloud = new int[n][n];
	     for(int x = 0; x < n; x++) {
	    	 for(int y = 0; y < n; y++) {
	    		 if (cloud[x][y] == 1) {
	    			 int nx = (x + dx[d] * s + n) % n;
	    			 int ny = (y + dy[d] * s + n) % n;
	    			 ncloud[nx][ny] = 1;

	    		 }
	    	 }
	     }
	     return ncloud;
	}
	
	public static void rain() {
		 for(int x = 0; x < n; x++) {
	    	 for(int y = 0; y < n; y++) {
	    		 if (cloud[x][y] == 1) {
	    			 arr[x][y] += 1;
	    		 }
	    	 }
	     }
	}
	
	public static void magic() {
		for(int x = 0; x < n; x++) {
	    	 for(int y = 0; y < n; y++) {
	    		 int res = 0;
	    		 if(cloud[x][y] == 1) {
	    			 for(int i = 0; i < 4; i++) {
	    				 int nx = x + dx2[i];
	    				 int ny = y + dy2[i];
	    				 if (nx < 0 || ny < 0 || nx >= n || ny >=n) {
	    					 continue;
	    				 }
	    				 if(arr[nx][ny] >= 1) {
	    					 res += 1;
	    				 }
	    				 
	    			 }
	    		 }
	    		 arr[x][y] += res;
	    	 
	    	 	}
	    	 }
		
	}
	
	public static int[][] make_cloud() {
		// 물 2이상인 칸&3에서 구름이 없는 경우 =>  구름 생기고, 바구니 -2
		int[][] ncloud = new int[n][n];
		for(int x = 0; x < n; x++) {
	    	 for(int y = 0; y < n; y++) {
	    		 if(arr[x][y] >= 2 && cloud[x][y] != 1) {
	    			 ncloud[x][y] = 1;
	    			 arr[x][y] -= 2;
	    		 }
	    	 }
	    	}
		
		return ncloud;
	}

}

 

 

5. 결론

• 구현 문제