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

Java

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

문제

접근 방법

문제를 푸는데 필요한 알고리즘들을 모듈화 하여 해결하였다.

1. 경계를 벗어나는 좌표를 계산해주는 메서드
2. 현재 좌표에서 4방향 대각선에 물이 존재하는 개수를 알려주는 메서드
   를 생성하여 코드의 가독성을 높였다.

주의할 점은 4방향 대각선에서 물이 존재하는지 확인할 때,
미리 map 배열을 따로 저장해두어서 대각선 개수만큼 물이 증가하는 것에 영향을 받지 않아야한다.

코드

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

public class Main {
	static int n, m, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	int[][] map = new int[n][n];
    	boolean[][] curCloud = new boolean[n][n];
    	boolean[][] nextCloud;
    	int[][] captureMap = new int[n][n];
    	
    	curCloud[n - 1][0] = true;
    	curCloud[n - 1][1] = true;
    	curCloud[n - 2][0] = true;
    	curCloud[n - 2][1] = true;
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
    	int dir, dist;
    	while(m-- != 0) {
    		stk = new StringTokenizer(br.readLine());
    		dir = stoi(stk.nextToken());
    		dist = stoi(stk.nextToken());
    		nextCloud = new boolean[n][n];
    		
    		// 1. 모든 구름이 di 방향으로 si칸 이동한다.
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(curCloud[i][j]) {
    					int[] pos = convertPos(i, j, dir, dist);
    					nextCloud[pos[0]][pos[1]] = true;
        			}
    			}
    		}
    		
    		// 2. 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(nextCloud[i][j])
    					map[i][j]++;
    			}
    		}
    		
    		// map이 변하기 직전을 캡처 해놓는다.
    		for(int i = 0; i < n; i++)
    			captureMap[i] = map[i].clone();
    		// 3. 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 증가
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(nextCloud[i][j])
    					map[i][j] += countWater(i, j, captureMap);
    			}
    		}
    		
    		curCloud = new boolean[n][n];
    		// 4. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다.
    		// 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(map[i][j] >= 2 && !nextCloud[i][j]) {
    					map[i][j] -= 2;
    					curCloud[i][j] = true;
    				}
    			}
    		}
    	}
    	
    	// 바구니에 들어있는 물의 양의 합
    	for(int i = 0; i < n; i++) {
    		for(int j = 0; j < n; j++) {
    			result += map[i][j];
    		}
    	}
    	
    	System.out.println(result);
    	br.close();
	}
	
	static int[] dy = new int[] {0, 0, -1, -1, -1, 0, 1, 1, 1};
	static int[] dx = new int[] {0, -1, -1, 0, 1, 1, 1, 0, -1};
	
	// 경계를 벗어나는 좌표를 계산해주는 메서드
	static int[] convertPos(int y, int x, int dir, int dist) {
		int[] result = new int[2];
		
		dist = dist % n;
		
		y = y + (dy[dir] * dist);
		x = x + (dx[dir] * dist);
		
		if(y < 0)
			y = n + y;
		else if(y >= n)
			y = y - n;
		
		if(x < 0)
			x = n + x; 
		else if (x >= n)
			x = x - n;
		
		result[0] = y;
		result[1] = x;
		return result;
	}
	
	// 현재 좌표에서 4방향 대각선에 물이 존재하는 개수를 알려주는 메서드
	static int countWater(int y, int x, int[][] map) {
		int cnt = 0;
		
		int[] dirY = new int[] {-1, -1, 1, 1};
		int[] dirX = new int[] {-1, 1, -1, 1};
		
		int ny, nx;
		for(int i = 0; i < 4; i++) {
			ny = y + dirY[i];
			nx = x + dirX[i];
			if(isIn(ny,nx) && map[ny][nx] >= 1)
				cnt++;
		}
		
		return cnt;
	}
	
	static boolean isIn(int y, int x) {
		if(0 <= y && y < n && 0 <= x && x < n)
			return true;
		return false;
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점