naknak

알고리즘/구현

BJ_G4_20058_마법사 상어와 파이어스톰 - Java

naksnaks 2022. 1. 30.
반응형

[문제링크]

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

 

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

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c

www.acmicpc.net

[문제]

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

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

마법을 시전하기 전 L = 1 L = 2

 

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

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

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

[입력]

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

[출력]

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

[예제 입력 1]

3 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1

[예제 출력 1]

284
64

 

[예제 입력 2]

3 2
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2

[예제 출력 2]

280
64

 

[예제 입력 3]

3 5
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 0 3 2

[예제 출력 3]

268
64

 

[예제 입력 4]

3 10
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 0 3 2 1 2 3 2 3

[예제 출력 4]

248
62

 

[예제 입력 5]

3 10
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 1 2 3 1 2 3 1

[예제 출력 5]

246
60

 

[예제 입력 6]

3 10
1 0 3 4 5 6 7 0
8 0 6 5 4 3 2 1
1 2 0 4 5 6 7 0
8 7 6 5 4 3 2 1
1 2 3 4 0 6 7 0
8 7 0 5 4 3 2 1
1 2 3 4 5 6 7 0
0 7 0 5 4 3 2 1
1 2 3 1 2 3 1 2 3 1

[예제 출력 6]

37
9

 

 

[설명]

이 문제는 구현 및 시뮬레이션 문제이다.

문제를 푸는 순서는

1. 행렬을 크기에 맞춰 회전시킨다.

2. 얼음을 녹인다.

3. 남은 얼음의 합과 가장 큰 덩어리의 크기를 구한다.

 

1) 회전의 경우 처음에 재귀함수를 활용하여 구현하려고 했다. 하지만 재귀함수보다 쉬운 방법으로 회전을 구현할 수 있다.

for문을 돌려서 회전을 몇번 반복해야하는지 구해야한다. 그 뒤 result배열에 값을 넣어준다.

예시를 들어서 설명해보자면,

(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)

위의 배열이 아래의 배열처럼 변한다.

(3,0) (2,0) (1,0) (0,0)
(3,1) (2,1) (1,1) (0,1)
(3,2) (2,2) (1,2) (0,2)
(3,3) (2,3) (1,3) (0,3)

 

(0,0) -> (3,0) / (0,1) -> (2,0) / (0,2) -> (1,0) / (0,3) -> (0,0) 이를 점화식으로 만들어보면,

arr2[i][j] = arr[length - 1 - j][i] 가 된다.

이 회전을 L의 크기에 따라 다르게 해야하기 때문에 각 배열의 입력값에 L의 크기에 따른 값을 추가하여 넣어주면,

arr2[startCol + i] [startRow + j] = arr[startCol + length - 1 - j][startRow + i]가 된다.

 

2) 얼음을 녹여보자.

얼음은 바로바로 녹이게 되면 값이 변경될 수 있기 때문에 boolean 배열을 추가하여 값을 저장해두고, 전부 한번에 바꿔준다.

이는 DFS를 사용하여 해결하였다.

 

3) 남은 얼음의 합과 가장 큰 덩어리의 크기를 구한다.

남은 얼음의 합은 그냥 arr 배열에 들어있는 값들을 전부 더해주면 된다.

가장 큰 덩어리의 크기는 BFS를 반복하여 그 길이를 측정한 뒤 max값을 변경해주면 해결된다.

 

백준 알고리즘 20058번 JAVA풀이

 

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 {

	static int N, Q, length;
	static int[][] arr;
	static int[] len;
	static int max_length = Integer.MIN_VALUE;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -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());
		Q = Integer.parseInt(st.nextToken());
		length = (int) Math.pow(2, N);
		arr = new int[length][length];
		len = new int[Q];
		for (int i = 0; i < length; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < length; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < Q; i++) {
			len[i] = Integer.parseInt(st.nextToken());
			len[i] = 1 << len[i];
		}
		
		for (int i = 0; i < Q; i++) {
			arr = tornado(len[i]);
			melt();
		}
		
		// 얼음 남은 개수
		int ice_left = 0;
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				if (arr[i][j] >= 0) {
					ice_left += arr[i][j];
				}
			}
		}

		largest();
		
		System.out.println(ice_left+"\n"+max_length);
	}

	private static void largest() {
		boolean[][] visited= new boolean[length][length];
		for(int r=0;r<length;r++) {
			for(int c=0;c<length;c++) {
				if(visited[r][c]) continue;
				int cnt=0;
				Queue<Node> q = new LinkedList<>();
				q.add(new Node(r,c));
				while(!q.isEmpty()) {
					Node temp = q.poll();
					for(int d=0;d<4;d++) {
						int nr=temp.r+dr[d];
						int nc=temp.c+dc[d];
						if(nr<0 || nr>=length || nc<0 || nc>=length) continue;
						if(visited[nr][nc] || arr[nr][nc]<=0) continue;
						visited[nr][nc]=true;
						cnt++;
						q.add(new Node(nr,nc));
					}
					max_length=Math.max(max_length, cnt);
				}
			}
		}
	}
	
	private static void melt() {
		boolean[][] visited = new boolean[length][length];
		
		for(int r=0;r<length;r++) {
			for(int c=0;c<length;c++) {
				int cnt=0;
				if(arr[r][c]==0) continue;
				for(int d=0;d<4;d++) {
					int nr=r+dr[d];
					int nc=c+dc[d];
					if(nr<0 || nr>=length || nc<0 || nc>=length) continue;
					if(arr[nr][nc]<=0) continue;
					cnt++;
				}
				if(cnt<3) visited[r][c]=true;
			}
		}
		for(int i=0;i<length;i++) {
			for(int j=0;j<length;j++) {
				if(visited[i][j]) arr[i][j]--;
			}
		}
	}

	public static int[][] tornado(int distance) {

		int[][] result = new int[length][length];

		for (int startRow = 0; startRow < length; startRow += distance) {
			for (int startCol = 0; startCol < length; startCol += distance) {
				for (int i = 0; i < distance; i++) {
					for (int j = 0; j < distance; j++) {
						result[startCol + i][startRow + j] = arr[startCol + distance - 1 - j][startRow + i];
					}
				}
			}
		}

		return result;
	}

	public static class Node {
		int r;
		int c;

		public Node(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

	}
}

 

 

 

아래의 블로그를 참조하여 문제를 해결하고, 작성했습니다.

내맘대로블로그

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.

 

반응형

'알고리즘 > 구현' 카테고리의 다른 글

BJ_G5_14719_빗물 - Java  (0) 2022.02.27
BJ_G5_20055_컨베이어 벨트 위의 로봇 - Java  (0) 2022.02.04
BJ_B2_15552_빠른A+B - Java  (0) 2022.01.20
SWEA(SW EXPERT ACADEMY) - 1954번 : 달팽이 숫자 - JAVA  (0) 2021.01.21
BOJ(백준알고리즘) - 10872번 : 팩토리얼 - JAVA  (2) 2021.01.19

댓글

💲 추천 글

티스토리툴바