[ 알고리즘 ] 코딩 - 백준 20058 - 마법사 상어와 파이어스톰.java

---

문제 링크

www.acmicpc.net/problem/20058

20058번: 마법사 상어와 파이어스톰

---

문제개요

백준 20058번 (자바) 마법사 상어와 파이어스톰 - 시뮬레이션 / 구현 / BFS 

크기가 2^N × 2^N인 격자로 나누어진 얼음판. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2^L × 2^L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다. 

( 이 부분때문에 국어 독해력을 의심해야만 했다... 쉽게 말하면 현재 자신의 위치에서 상 / 하 / 좌 / 우 위치를 봤을 때 존재하는 얼음이 2개 이하라면 자신도 1 줄어든다. 자신을 포함했다면 3개 이하 )

회전 예시

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

---

 

로직

Step 00. 입력을 받아서 N과 L을 미리 2제곱 해서 저장하자.

Step 01. L이 1이 아닌 경우라면 N을 L 크기만큼 나눈 다음 90도 회전을 하자. 이때 DFS를 이용해서 4부분으로 나누었다. N과 L이 같다면 map의 영역을 복사해서 그 영역을 기준으로 회전시켜 주었다.

Step 02. 회전을 하고난 map 전체를 기준으로 맵 전체의 얼음을 탐색한다. 현재 얼음의 4방향을 봤을 때 얼음의 수가 2개 이하라면 현재 위치의 얼음을 -1 해준다. 이 과정을 2중 for문을 순회하며 연쇄적으로 했었는데 문제에서 요구하는 것은 연쇄가 아닌 모든 위치를 기록하고 한번에 녹이는 것이다. 그러므로 2중 for문을 순회하며 주위 얼음의 수가 2개 이하인 경우 현재 얼음의 위치를 기록하고, 2중 for문이 끝난 뒤에 기록된 모든 얼음을 -1 해주면 된다.

Step 03. Step 01 ~ Step 02를 Q번 반복한다.

Step 04. Step 03이 끝나고 난 후의 map을 기준으로 가장 큰 덩어리와 모든 얼음의 합을 구한다. 2중 for문을 순회하며 BFS로 덩어리를 탐색한다. 이때, 최대 덩어리를 비교하기위해 max_lump와 비슷한 것을 하나 두게 되는데 초기화를 Integer.MIN_VALUE로 해놓으면 45%~46%정도에서 틀렸습니다를 만나게 된다. 이는 덩어리가 없는 경우가 있을수도 있기 때문에 0으로 초기화 해주면 해결이 된다.

Step 05. Step 04에서 나온 덩어리와 합을 출력하면 정답!

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stt = new StringTokenizer(br.readLine());
		// 맵 크기
		int N = (int) Math.pow(2, Integer.parseInt(stt.nextToken()));
		// 시전 횟수
		int Q = Integer.parseInt(stt.nextToken());

		int[][] map = new int[N][N];
		for(int i = 0; i < N; i++) {
			stt = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(stt.nextToken());
			}
		} 
		
		// 시전 단계
		int[] L = new int[Q];
		stt = new StringTokenizer(br.readLine());
		for(int i = 0; i < Q; i++) {
			L[i] = (int) Math.pow(2, Integer.parseInt(stt.nextToken()));
		} // input end
		
		process(N, Q, map, L);
		
		// 녹인 얼음을 기준으로 덩어리를 찾자!
		int[] res = findLump(map, N);
		
		System.out.println(res[0]);
		System.out.println(res[1]);
	}

	private static void process(int n, int q, int[][] map, int[] l) {
		// q번 반복
		for(int i = 0; i < q; i++) {
			// L 크기 만큼 90도 배열 돌리기
			int level = l[i];
			rotate(map, level, n, 0, 0);
			
			// 얼음을 녹이자!
			meltIce(map, n);
		}
	}
	
	private static int[] findLump(int[][] map, int n) {
		int[] dy = {-1, 1, 0, 0};
		int[] dx = {0, 0, -1, 1};
		boolean[][] visited = new boolean[n][n];
		int sum = 0;
		int lump = 0;
		int max_lump = 0;
		
		// BFS로 덩어리를 찾고, 모든 얼음을 더한다.
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				sum += map[i][j];
				if(map[i][j] == 0) continue;
				if(visited[i][j]) continue;
				Queue<int[]> ice_queue = new LinkedList<int[]>();
				ice_queue.offer(new int[] {i, j});
				visited[i][j] = true;
				lump = 0;
				
				while(!ice_queue.isEmpty()) {
					int[] cur_ice = ice_queue.poll();
					int y = cur_ice[0];
					int x = cur_ice[1];
					lump++;
					
					for(int d = 0; d < 4; d++) {
						int next_y = y + dy[d];
						int next_x = x + dx[d];
						
						if(rangeCheck(next_y, next_x, n)) continue;
						if(map[next_y][next_x] == 0) continue;
						if(visited[next_y][next_x]) continue;
						ice_queue.offer(new int[] {next_y, next_x});
						visited[next_y][next_x] = true;
					}
				} // while end
				// 가장 큰 덩어리 갱신
				max_lump = max_lump > lump ? max_lump : lump;
			} // for j end
		} // for i end
		int[] res = {sum, max_lump};
		return res;
	}

	// 주위 4방향을 봤는데 얼음이 없다면 녹인다.
	private static void meltIce(int[][] map, int n) {
		int[] dy = {-1, 1, 0, 0};
		int[] dx = {0, 0, -1, 1};
		List<int[]> list = new LinkedList<int[]>();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(map[i][j] == 0) continue;
				
				// 주위 4방향 얼음 확인
				int ice_cnt = 4;
				for(int d = 0; d < 4; d++) {
					int next_y = i + dy[d];
					int next_x = j + dx[d];
					if(rangeCheck(next_y, next_x, n)) {
						ice_cnt--;
						continue;
					}
					if(map[next_y][next_x] == 0) {
						ice_cnt--;
						continue;
					}
				}
				// 녹일 위치 저장
				if(ice_cnt <= 2) {
					list.add(new int[] {i, j});
				}
			}
		} // for i end
		
		// 해당 위치의 얼음을 녹인다.
		for(int[] position: list) {
			int y = position[0];
			int x = position[1];
			if(map[y][x] > 0) {
				map[y][x]--;
			}
		}
	}

	// 밤위 체크
	private static boolean rangeCheck(int next_y, int next_x, int n) {
		return next_y < 0 || next_y >= n || next_x < 0 || next_x >= n;
	}
	
	private static void rotate(int[][] map, int l, int n, int y, int x) {
		if(n == l) { // 현재 N이 L과 같다면
			int[][] init_map = new int[n][n];
			int idx_y = 0; // init_map y 인덱스
			for(int i = y; i < n+y; i++) {
				int idx_x = 0; // init_map x 인덱스
				for(int j = x; j < n+x; j++) {
					init_map[idx_y][idx_x++] = map[i][j];
				}
				idx_y++;
			}
			
			// 90도 회전
			idx_y = 0;
			for(int i = y; i < n+y; i++) {
				int idx_x = 0;
				for(int j = x; j < n+x; j++) {
					map[i][j] = init_map[n-1-idx_x++][idx_y];
				}
				idx_y++;
			}
			
			return ;
		}
		
		// 총 4부분으로 나누어짐
		rotate(map, l, n/2, y, x); // 왼쪽위
		rotate(map, l, n/2, y, x+n/2); // 오른족 위
		rotate(map, l, n/2, y+n/2, x); // 왼쪽 아래
		rotate(map, l, n/2, y+n/2, x+n/2); // 오른족 아래
	}
}