[구현] 마법사 상어와 파이어스톰(백준 20058번, 자바)☆

 

20058번: 마법사 상어와 파이어스톰 (acmicpc.net)

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

 

문제

마법사 상어는파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 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)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

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

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

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

 

입력

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

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

출력

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

 

구현 

1. 맵의 회전(4중 for문을 사용하여 배열을 회전시킨다.

for (int x = 0; x < N; x += size) {
			for (int y = 0; y < N; y += size) {
				for(int i=0;i<N;i++) {
					for(int j=0;j<N;j++) {
						temp[x+i][y+j]=map[x+size-1-j][y+i];
					}
				}
			}
		}

 

2. bfs를 이용하여 얼음이 있는 칸 3개 이상과 인접한 구역이 있는지 확인하고, 그렇지 않은 경우 값을 -1한다.

 

	static void checkZero() {
		
		Queue<int[] >q=new LinkedList<>();
		
		for(int i=0;i<size1;i++) {
			
			
			for(int j=0;j<size1;j++) {
				
				if(map[i][j]==0) continue;	
				int cnt=0; //얼음이 없는 칸의 수
				for(int x=0;x<4;x++) {
					int nx=i+dx[x];
					int ny=j+dy[x];
					
					if(nx<0 || nx>=size1 || ny<0 || ny>=size1 || map[nx][ny]==0) continue;
					
					cnt++;	
				}
				
				if(cnt<3) q.add(new int[] {i,j});
			}
		}
		
		while(!q.isEmpty()) {
			int[] n =q.poll();
			map[n[0]][n[1]]--;
		}
	}

 

3. bfs를 이용하여 큰 덩어리가 차지하는 칸의 개수를 계산한다. 

static int getResult2() {
		
		int answer=0;
		boolean[][] visit=new boolean[size1][size1];
		Queue<int[]> q=new LinkedList<>();
		
		for(int i=0;i<size1;i++) {
			for(int j=0;j<size1;j++) {
				int cnt=0;
				if(!visit[i][j] && map[i][j]!=0) {
					q.add(new int[] {i,j});
					visit[i][j]=true;
					
					while(!q.isEmpty()) {
						int[] n=q.poll();
						cnt++;				
						for(int x=0;x<4;x++) {
							int nx=n[0]+dx[x];
							int ny=n[1]+dy[x];		
							if(nx<0 || ny<0 || nx>=size1 || ny>=size1 || visit[nx][ny] || map[nx][ny]==0) continue;
							visit[nx][ny]=true;
							q.add(new int[] {nx,ny});
						}
					}
					answer=Math.max(answer,cnt);
				}
				
			}
		}	
		return answer;
	}