BOJ - 마법사 상어와 파이어스톰 20058번 (JAVA)

❓ 문제 - 백준 마법사 상어와 파이어스톰 20058번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/20058)

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

 

 

 

📝 문제해결법

1. 이 문제는 구현+BFS으로 풀었다.

• 구역 나눠서 90도를 회전하는 부분에서 각 2^N X 2^N 격자에서 L구열으로 나누어서 구역 시작 열과 행 r, c를 기준으로 구열을 90도 회전 처리한다.
• rotate 함수를 통해 90도 회전 시키며 각 구열의 길이와, 시작 위치를 반영해서 맞춰서 구현해줬다.
• 얼음양을 조절하는데 우선 얼음의 양이 줄어드는 건 동시에 일어나므로 map_copy를 통해 남은 얼음의 양을 저장한다.
• 인접한 4 방향에서 만약 얼음이 주변에 3개 이상 없으면 해당 구역은 얼음의 수가 1 감소 처리한다.
• 남아있는 얼음 중에 가장 큰 덩어리를 차지하는 칸의 개수를 구할 때는 BFS를 활용하며 가장 얼음이 긴 구역의 길이의 최대값을 갱신한다.

 

 

💻 소스코드

// BOJ - 마법사 상어와 파이어스톤(20058번)
// 구현 + BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_20058 {
	public static int n, nn, max_cnt;
	public static int[][] map;
	public static boolean[][] visited;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		nn = (int) Math.pow(2, n);
		map = new int[nn][nn];
	
		visited = new boolean[nn][nn];
		for(int i=0;i<nn;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<nn;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int p=0;p<q;p++) {
			int l = Integer.parseInt(st.nextToken());
			// 구역 나눠서 90도 회전
			int a = (int)Math.pow(2, l);
			int end = nn / a;
			int[][] temp = new int[nn][nn];
			for(int i=0;i<nn;i+=a) {
				for(int j=0;j<nn;j+=a) {
					rotate(i, j, a, temp);
					
				}
			}
			map = temp;
		
			// 얼음 양 조절
			int[][] map_copy = new int[nn][nn];
			
			for(int i=0;i<nn;i++) {
				for(int j=0;j<nn;j++) {
					if(map[i][j] == 0) continue;
					int ice_cnt = 0;
					for(int d=0;d<4;d++) {
						int nx = i + dx[d];
						int ny = j + dy[d];
						if(0 <= nx && nx < nn && 0 <= ny && ny < nn) {
							if(map[nx][ny] > 0) ice_cnt++;
						}
					}
					if(ice_cnt < 3) {
						map_copy[i][j] = map[i][j] -1;
					} else {
						map_copy[i][j] = map[i][j];
					}
				}
				
			}
			map = map_copy;
		}
		
		// 남은 얼음 계산, 얼음 덩어리 최대
		int ans = 0;
		max_cnt = 0;
		for(int i=0;i<nn;i++) {
			for(int j=0;j<nn;j++) {
				ans += map[i][j];
				if(!visited[i][j] && map[i][j] != 0) {
					bfs(i, j);
				}
			}
		}

		System.out.println(ans);
		System.out.println(max_cnt);
		
		
		
	}
	
	public static void rotate(int r, int c, int l, int[][] temp) {
		for(int i=0;i<l;i++) {
			for(int j=0;j<l;j++) {
				temp[r+i][c+j] = map[r+l-j-1][c+i];
			}
		}
	}
	
	public static void print() {
		for(int i=0;i<nn;i++) {
			for(int j=0;j<nn;j++) {
				System.out.print(map[i][j] +" ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	
	public static void bfs(int x, int y) {
		int cnt =1;
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {x, y});
		visited[x][y] = true;
		while(!q.isEmpty()) {
			int[] arr = q.poll();
			for(int d=0;d<4;d++) {
				int nx = arr[0] + dx[d];
				int ny = arr[1] + dy[d];
				if(nx < 0 || nx >= nn || ny < 0 || ny >= nn) continue;
				if(!visited[nx][ny] && map[nx][ny] != 0) {
					visited[nx][ny] = true;
					cnt++;
					q.add(new int[] {nx, ny});
				}
			}
		}
		
		max_cnt = Math.max(cnt, max_cnt);
	}

}