[백준_20058번] 마법사 상어와 파이어스톰_삼성 SW 역량테스트

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

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가 순서대로 주어진다.

 

[코드]

import java.util.*;

class Point_20058 {
	int x,y;
	
	public Point_20058(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class BaekJoon_20058 {
	static int[][] map;
	static boolean[][] visited;
	static int n,q,size,sum,max=0;
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		q=sc.nextInt();
		size=(int)Math.pow(2, n); // 맵 가로, 세로 크기
		map=new int[size][size];
		
		// 2^N × 2^N인 격자 채우기
		for(int i=0;i<size;i++)
			for(int j=0;j<size;j++)
				map[i][j]=sc.nextInt();
		
		for(int i=0;i<q;i++) {
			int l=sc.nextInt();
			
			rotate(l);
			melt();
		}
		
		// 해당 얼음이 어떤 얼음덩이에 속해있는지 확인하는 방문 체크 배열
		visited=new boolean[size][size]; 
		for(int i=0;i<size;i++) {
			for(int j=0;j<size;j++) {
				// 아직 어떤 그룹에도 속해있지 않으면서 얼음이 있는 곳에서부터 그룹 생성
				if(!visited[i][j]&&map[i][j]>0) {
					visited[i][j]=true; // 방문처리
					max=Math.max(max,dfs(i,j)); // 가장 큰 얼음덩어리가 차지하는 칸수 갱신
				}
			}
		}
		
		System.out.println(sum+"\n"+max);
	}
	
	// 가장 큰 얼음 덩어리와 전체 얼음의 양을 구하는 함수
	static int dfs(int x, int y) {
		int count=1; // 시작 좌표를 포함해야 함으로 1로 초기화
		sum+=map[x][y]; // 전체 얼음의 양 구하기
		
		for(int i=0;i<4;i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			// 탐색하고자 하는 곳이 배열 범위 내에 있으며
			if(nx>=0&&ny>=0&&nx<size&&ny<size) {
				// 얼음이 있고 아직 어떤 그룹에도 속하지 않았다면
				if(map[nx][ny]>0&&!visited[nx][ny]) {
					visited[nx][ny]=true; // 방문처리
					count+=dfs(nx,ny); // 칸수 누적
				}
			}
		}
		return count; // 칸수 return
	}
	
	// 얼음 덩어리를 녹이는 함수
	static void melt() {
		// 녹여야 하는 얼음의 좌표가 들어있는 칸
		Queue<Point_20058> q=new LinkedList<>();
		
		for(int x=0;x<size;x++) {
			for(int y=0;y<size;y++) {
				int count=0; // 얼음과 인접해있는 칸의 개수
				
				// 상,하,좌,우 탐색
				for(int d=0;d<4;d++) {
					int nx=x+dx[d];
					int ny=y+dy[d];
					
					if(nx>=0&&ny>=0&&nx<size&&ny<size) 
						if(map[nx][ny]>=1) // 얼음이 있는 칸
							count++;
				}
				// 3칸 이상 얼음이 있는 칸과 인접해 있지 않다면
				if(count<3) 
					q.offer(new Point_20058(x,y)); // 큐에 삽입
			
			}
		}
		
		// 큐에 있는 좌표들을 녹야아하는 얼음의 좌표가 들어있으므로 얼음의 양 1 줄이기
		while(!q.isEmpty()) {
			Point_20058 p=q.poll();
			
			map[p.x][p.y]--;
		}
	}
	
	// 격자를 90도 회전하는 함수
	static void rotate(int l) {
		int[][] temp=new int[size][size]; // 회전된 배열을 저장할 임시 배열
		int loop=size/(int)Math.pow(2, l); // 맵의 한 변의 크기 / 격자의 한 변의 크기
		
		int x=0;
		// 세로
		for(int i=0;i<loop;i++) {
			int y=0;
			
			if(i!=0)
				x+=(int)Math.pow(2, l); // 다음 회전 시작할 x 좌표 구하기
			
			// 가로
			for(int j=0;j<loop;j++) {
				
				if(j!=0)
					y+=(int)Math.pow(2, l); // 다음 회전 시작할 y 좌표 구하기
				
				// 한 격자의 좌표 값들 90도 회전시키기
				for(int a=0;a<(int)Math.pow(2, l);a++)
					for(int b=0;b<(int)Math.pow(2, l);b++)
						temp[x+b][y-a+(int)Math.pow(2, l)-1]=map[x+a][y+b];
			}
		}
		map=temp;
	}
}

 

[문제]

 이번 문제는 BFS+DFS+구현이 섞여있는 전형적인 삼성 문제로 구현 부분이 가장 어려웠던 문제였다. 항상 느끼는거지만 배열의 인덱스를 다루는 부분이 많이 약한것 같다. 여러 구현 문제를 풀어보면서 보완해야하는 걸 알지만 쉽지 않은것 같다. 좀 더 노력해야할 부분이라고 다시한번 느꼈다. 

 

*** 1) 격자 회전시키기(rotate 함수) - 구현

 이번 문제에서 구현 부분에 해당하는 부분으로 가장 어렵게 느껴졌던 부분이다. 따로 사용해야 하는 알고리즘은 없고, 그림을 그려 직접 인덱스를 써가면서 구현한다면 헷갈리지 않게 풀 수 있을 것이다.

 

*** 2) 얼음을 녹이기(melt 함수) - BFS 알고리즘

 2-1) 전체 얼음을 탐색하면서 각 칸마다 인접한 얼음이 있는 칸의 개수를 구한다.

 2-2) 탐색 좌표의 상, 하, 좌, 우를 탐색하면서 얼음이 있는 칸의 개수를 count 한다.

 2-3) 인접한 얼음이 있는 칸의 개수가 3칸 이상이 아니라면 해당 좌표를 큐에 삽입한다.

 2-4) 큐에 있는 값들을 모두 꺼내면서 해당 좌표의 얼음 크기를 1 감소시킨다.

 

*** 3) 전체 얼음의 양과 얼음이 차지하는 칸 수 구하기 - DFS 알고리즘

 3-1) 얼음 그룹에 속했는지의 여부를 판단하기 위한 visited 배열을 사용한다.

 3-2) 전체 맵을 탐색하면서 아직 그룹에 속해있지 않고, 얼음이 있는 칸부터 그룹을 형성한다.

 3-3) 탐색 시작 좌표부터 상, 하, 좌, 우를 탐색하다가 아직 그룹에 속해있지 않고, 얼음이 있는 칸이라면 그룹에 포함시키고(visited 방문처리), 칸의 개수를 누적한다.

 3-4) 함수가 한 번 실행될 때 마다 하나의 얼음 그룹을 구한것이기 때문에 최대 칸수의 개수를 갱신한다.