20058_마법사 상어와 파이어스톰

사용 알고리즘: bfs

사용 언어: java

 

package week38;

import java.util.*;
public class Main_bj_20058_마법사상어와파이어스톰 {
	static int N, Q, map[][], n;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		Q = sc.nextInt();
		n = (int) Math.pow(2, N);
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		///
		for (int q = 0; q < Q; q++) {
			int L = sc.nextInt();
			int l = (int) Math.pow(2, L);
			//구역나누기
			  //구역마다 90도 회전
			for (int i = 0; i < n; i = i + l) {
				for (int j = 0; j < n; j = j + l) {
					int[][] tmp = fireStorm(i, j, l);
					turn90(i,j, l, tmp);
				}
			}
			//사방탐색, 녹을 얼음 지정
			boolean[][] melt = isMelt();
			//녹이기
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if(melt[i][j]) {
						map[i][j]--;
					}
				}
			}
		}
		
		int answer = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				answer += map[i][j];
			}
		}
		System.out.println(answer);
		
		
		answer = 0;
		boolean[][] visit = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(map[i][j] > 0 && !visit[i][j]) {
					visit[i][j] = true;
					answer = Math.max(answer, findArea(i,j, visit));
				}
			}
		}
		System.out.println(answer);
		//
	}

	private static int findArea(int x, int y, boolean[][] visit) {
		int area = 0;
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {x,y});
		int[] dx = {-1,1,0,0};
		int[] dy = {0,0,-1,1};
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			area++;
			
			for (int d = 0; d < 4; d++) {
				int nx = p[0] + dx[d];
				int ny = p[1] + dy[d];
				
				if(nx>=0&&nx<n && ny>=0&&ny<n && !visit[nx][ny] && map[nx][ny] > 0) {
					visit[nx][ny] = true;
					q.add(new int[] {nx,ny});
				}
			}
		}
		
		return area;
	}

	private static boolean[][] isMelt() {
		boolean[][] melt = new boolean[n][n];
		int[] dx = {-1,1,0,0};
		int[] dy = {0,0,-1,1};
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(map[i][j] <= 0) continue;
				//i, j
				int cnt = 0; //얼음이 있는 개수
				for (int d = 0; d < 4; d++) {
					int nx = i + dx[d];
					int ny = j + dy[d];
					
					if(nx>=0&&nx<n && ny>=0&&ny<n && map[nx][ny] >= 1)
						cnt++;
				}
				
				if(cnt < 3) melt[i][j] = true;
			}
		}
		return melt;
	}

	private static void turn90(int x, int y, int l, int[][] tmp) {
		//맵[x+][y+] = tmp[i][j];
		for (int i = 0; i < l; i++) {
			for (int j = 0; j < l; j++) {
				map[j+x][l-1-i+y] = tmp[i][j];
			}
		}
	}

	private static int[][] fireStorm(int x, int y, int l) {
		int[][] tmp = new int[l][l];
		for (int i = 0; i < tmp.length; i++) {
			for (int j = 0; j < tmp.length; j++) {
				tmp[i][j] = map[i+x][j+y];
			}
		}
		return tmp;
	}
}

 

 

구현 자체는 어렵지 않음.

나 같은 경우, 한 번 틀림. (이미 얼음이 없는 상태에서도 계속 마이너스를 하여서, 남아있는 얼음의 개수(?)를 카운트 할 때 마이너스가 나오는 참사가 벌어짐.... isMelt() 함수에서, 현재 얼음이 없다면(map[i][j]가 0보다 작다면) 사방탐색 필요 없이 그냥 넘어가게 함으로써 이 문제를 해결함)