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

문제

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

 

풀이 방법

문제에 따라서 순서대로 차근차근 구현해갔다. 
문제에서 주목해야할 점은
1. 구름이 이동할 때 범위에 신경써야 하는 것
2. 대각선 방향을 확인할때의 범위는 또 다르게 적용된다는 것
3. 한꺼번에 처리하려다가 오히려 잘못된 값이 나올 수 있다는 점
이 세가지인 듯 하다. 

나는 구현하는 건 어렵지 않았지만 3번 때문에 디버깅하는데 조금 시간이 걸렸다.
그리고 격자도 그렇고, 방향도 그렇고 인덱스 1부터 시작하는걸 나는 0부터 시작하는 걸로 수정해서 구현했다.
전제적인 과정을 정리하면 다음과 같다.

1. 처음에 구름 생성해주기
2. M번 이동 실행하기
   1) 모든 구름을 올바른 방향으로 이동 시키기
   2) 물의 양 증가시키기
   3) 구름 제거하기
   4) 물 복사버그마법 시전
   5) 추가 구름 생성해주기

나는 Queue를 사용해서 구름의 정보를 저장했는데 다른 사람들 코드 보니 배열로 표시해두는 사람도 있었다. 

 

제출 코드

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

public class BOJ_21610_마법사상어와비바라기 {
	public static void main(String[] args) throws IOException {
		int[][] move = {{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}};
		int[][] side = {{-1,-1},{-1,1},{1,1},{1,-1}};
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] map =new int[N][N]; //현재 맵 정보
		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());
			}
		}
		
		int[][] move_info = new int[M][2]; //이동 정보 
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			move_info[i][0] = Integer.parseInt(st.nextToken())-1;
			move_info[i][1] = Integer.parseInt(st.nextToken());
		}
		
		//비바라기 시전
		Queue<int[]> que = new LinkedList<int[]>(); //구름들 저장
		//처음 구름 생성
		int[][] first = {{N-2, 0},{N-2,1},{N-1,0},{N-1,1}}; //처음에 생성될 구름의 위치들
		for (int i = 0; i < 4; i++) {
			que.offer(new int[] {first[i][0], first[i][1]});
		}
		
		for (int m = 0; m < M; m++) { //M번 이동
			//이동
			boolean[][] visit = new boolean[N][N];
			int cn = que.size();
			for (int i = 0; i < cn; i++) { //모든 구름 이동 시키기
				int ni = que.peek()[0] + move[move_info[m][0]][0] * move_info[m][1];
				int nj = que.poll()[1] + move[move_info[m][0]][1] * move_info[m][1];
				if(ni<0) ni = (ni+N*50)%N; else if(ni>=N) ni = ni%N; //1행 N행이 연결 되어있으므로
				if(nj<0) nj = (nj+N*50)%N; else if(nj>=N) nj = nj%N; 
				que.offer(new int[] {ni, nj});
				map[ni][nj]++; //구름이 있는 칸에 물 1 증가
			}
			
			int n = que.size();
			//구름 제거 및 대각선 정보 파악해서 물 더해주기
			for (int c = 0; c < n; c++) {
				int i = que.peek()[0], j = que.poll()[1];
				visit[i][j] = true; //구름 사라진 위치 표시 후 제거
				int cnt=0;
				for (int k = 0; k < 4; k++) { //대각선 정보 파악하기
					int ni = i+side[k][0]; 
					int nj = j+side[k][1]; 
					if(ni>=0 && ni<N && nj>=0 && nj<N && map[ni][nj] >0) cnt++;
				}
				map[i][j]+= cnt;
			}
			//구름 생성
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(map[i][j]>=2 && !visit[i][j]) {
						que.offer(new int[] {i,j});
						map[i][j]-=2;
					}
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < N; i++) { //모든 물의 양 구하기
			for (int j = 0; j < N; j++) {
				ans+=map[i][j]; 
			}
		}
		System.out.println(ans);
	}
}