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

문제

• BOJ 21610
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

처음에 구름의 좌표가 정해져있으므로 이를 gList에 넣고 아래를 수행한다.

1. 모든 구름이 d방향으로 s칸 이동한다.
   • 처음에 구름리스트 gList에 구름값을 세팅한 후 하나씩 꺼내서 다음좌표를 구해 tmpList에 넣는다.
   • 모든 구름을 구하면 gList를 초기화시킨후 tmpList의 값을 gList에 넣고, groom[][]에 true표시한다.
2. 구름에 있는 물 1증가
   • gList를 돌면서 map[][]값을 하나 증가시킨다.
3. 구름이 모두 사라진다.
   • map값에 구름을 표시하지않고 리스트로 따로 관리중이므로 이에 대한 코드작성할 필요가 없었다.
4. 물이 증가했던 곳에 물복사버그를 수행하는데, i,j로 부터 대각선 길이가 1인칸의 수를 구하고 map[i][j]에 누적시킨다.
   • gList에서 하나씩 꺼낸 후 대각선방향의 다음 좌표를 구한다.
   • 다음 좌표가 범위안에 들고 물이 있으면 cnt를 증가시킨다.
   • 모든 대각선 탐색 후 구한 cnt만큼 map[p.x][p.y]에 누적시킨다.
5. 새로운 구름을 생성해준다.
   • gList를 초기화시키고 전체map[][]을 돌면서 물이 2이상이고 groom[][]이 true가 아니면 이때의 좌표를 gList에 넣는다.
6. 1~5까지 M번 수행이 끝나면 map[][]을 돌면 서 남은 물의 합을 구해 출력한다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M;
	static int[][] map;
	static boolean[][] visited;
	static boolean[][] groom; //구름있는곳 표시 
	static List<Point> gList;
	static int d, s; // 방향, 속력
	static int[][] dArr = { { 0, -1 }, { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 } };
	static int[][] dArr2 = { { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } };
	static int Ans;

	static class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	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+1][N+1];
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}//End input
		
		//초기 구름 세팅
		gList = new ArrayList<>();
		gList.add(new Point(N, 1));
		gList.add(new Point(N, 2));
		gList.add(new Point(N-1, 1));
		gList.add(new Point(N-1, 2));
		
		for(int m=0; m<M; m++) {
			st = new StringTokenizer(br.readLine());
		    d = Integer.parseInt(st.nextToken()) - 1;
			s = Integer.parseInt(st.nextToken());
			
			//1. 모든 구름이 d방향으로 s칸 이동한다.
			List<Point> tmpList = new ArrayList<>(); //이동 후 구름 임시 저장
			visited = new boolean[N+1][N+1];
			groom = new boolean[N+1][N+1];
			
			for(Point p : gList) {
				int nx = p.x + dArr[d][0] * s%N;
				int ny = p.y + dArr[d][1] * s%N;
				
				if(nx < 1) nx += N;
				if(nx > N) nx %= N; 
				if(ny < 1) ny += N; 
				if(ny > N) ny %= N;
				
				if(visited[nx][ny]) continue;
				visited[nx][ny] = true;
				
				tmpList.add(new Point(nx, ny));
				groom[nx][ny] = true;
			}
			
			gList.clear();
			for(Point p : tmpList) gList.add(p);
			
			//2. 구름에 있는 물 1증가
			for(Point p : gList) map[p.x][p.y]++;
			
			//3. 구름 모두 사라짐
			
			//4. 물이 증가했던 곳에 물복사버그: i,j의 대각선1인 칸에 map[i][j]만큼 물 증가
			for(Point p : gList) {
				int cnt = 0;
				//대각선 거리1인 개수 찾기
				for(int d=0; d<4; d++) { 
					int nx = p.x + dArr2[d][0];
					int ny = p.y + dArr2[d][1];
					
					if(nx>=1 && nx<=N && ny>=1 && ny<=N && map[nx][ny] > 0) {
						cnt++;
					}
				}
				//물 복사
				map[p.x][p.y] += cnt;
			}
			
			gList.clear();
			//5. 물이 2이상인 곳에 구름 생성하고 물-2. 단 gList에 있는 좌표 아니어야함
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					if(map[i][j] >= 2 && !groom[i][j]) {
						map[i][j] -= 2;
						gList.add(new Point(i, j)); //구름 생성
					}
				}
			}
		}
		//남아있는 물의 합 구하기
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++){
				Ans += map[i][j];
			}
		}
		System.out.println(Ans);
	}
}