[백준] 20058 - 마법사 상어와 파이어스톰 (JAVA)

1. 소요시간 : 1시간 8분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 3
4. 문제 유형 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시뮬레이션, 깊이 우선 탐색
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 문제 링크 : https://www.acmicpc.net/problem/20058
7. 푼 날짜 : 2023.05.05

1. 사용한 자료구조 & 알고리즘

분할 정복, 재귀, DFS, 구현, 시뮬레이션, 그래프 이론, 그래프 탐색

2. 사고과정

1. 맵의 크기를 어떻게 쪼갤 것인가?
-> 분할정복과 재귀를 통해서 맵을 쪼갰다. 이전에 색종이 만들기

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

문제에서 분할 정복에 대해서 공부했었는데 이것이 도움이 됐다. 크기 L이 주어지면 그것에 맞게 4등분 해줌으로써 크기를 구할 수 있었다. 이 때, L 사이즈에 해당되게 잘라진 것들은 딱 1번만 구하면 된다. 그래서 1번 구해진 이후로는 다시 구하지 않도록 boolean 형의 visited[]로 체크했다. 구한 것은 L 인덱스의 ArrayList에 저장했다.

2. 어떻게 90도 회전시킬 것인가?
힘들 줄 알았는데 생각보다 별 것 없었다.

인덱스를 통해서 보니 i와 j 정도만 잘 바꿔서 처리하면 규칙을 찾아서 금방 처리할 수 있었다.
가로축은 [3,0], [2,0] , [1,0] , [0,0] 으로 앞의 숫자가 줄어들고
세로축은 [3,0] , [3,1] , [3,2] , [3,3] 으로 뒤의 숫자가 커지는 형태였다. 이의 규칙을 찾아주면 됐다.

3. 가장 많이 이어진 얼음은 어떻게 구할 것인가?
이건 문제 좀 풀어본 분들이라면 모두 dfs/bfs를 잘 떠올렸을 것이다.
나는 dfs를 통해서 count를 늘려주는 식으로 구현했다.

3. 풀이과정

1. 파이어볼스톰이 수행되면, L 크기의 visited가 false면 분할정복과 재귀를 이용해서 해당 크기에 해당하는 2차원 인덱스(y,x)를 ArrayList에 저장한다.
2. 구해진 ArrayList를 통해서 배열을 뒤집는다.
3. 주변을 확인하고 얼음이 3개 이상 있지 않은 얼음은 1칸 녹는다.
4. 파이어스톰이 Q번 수행되면, 남아있는 얼음을 모두 더한 sum 구한다.
5. dfs를 수행해서 가장 큰 덩어리의 얼음을 구한다.

4. 소스코드

import java.util.*;
import java.io.*;


public class Main{
	static int map[][];
	static int count = 0;
	static ArrayList<Integer[]> list[];
	static boolean dfsVisited[][];
	
	static int dy[]= {-1,1,0,0};
	static int dx[]= {0,0,-1,1};
	
	
	public static void main(String[] args) throws IOException{

		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());

		int N=Integer.parseInt(st.nextToken());
		int Q=Integer.parseInt(st.nextToken());
		int size=(int) Math.pow(2,N);
		list=new ArrayList[N+1];
		for(int i=0;i<=N;i++) 
			list[i]=new ArrayList<>();
		
		boolean visited[]=new boolean[N+1];
		map=new int[size][size];
		dfsVisited=new boolean[map.length][map.length];

		for(int i=0;i<size;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<size;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		st=new StringTokenizer(br.readLine());

		for(int i=0;i<Q;i++) {
			int L = Integer.parseInt(st.nextToken());
			
			//해당 크기로 나누어 진 적이 없다면, 해당 크기로 map을 나눈다.
			if(!visited[L]) {
				visited[L]=true;
				divide(0,0,size,L);
			}
			//회전한다.
			spin(L);
			//얼음을 녹인다.
			meltIce();

		}
		//얼음의 합계를 구한다.
		int sum = calMax();
		
		//dfs를 통해서 이어진 얼음의 길이를 구한다.
		int max = 0;
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map.length;j++) {
				if(!dfsVisited[i][j]&&map[i][j]>0) {
					count = 0;
					dfs(i,j);
					max=Math.max(count,max);
				}
			}
		}
		
		
		System.out.println(sum);
		System.out.println(max);
		



	}
	//얼음을 녹이는 메소드
	public static void meltIce() {
		int temp[][]=new int[map.length][map.length];
		
		//주변에 얼음이 몇개있나 체크
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map.length;j++) {
				
				for(int k=0;k<4;k++) {
					int nextY=i+dy[k];
					int nextX=j+dx[k];
					if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
						continue;
					if(map[nextY][nextX]==0) continue;
					
					temp[i][j]++;
					
				}
			}
		}
		//2개 이하면 얼음을 녹인다.
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map.length;j++) {
				if(temp[i][j]<3) {
					map[i][j] --;
					if(map[i][j]== -1) map[i][j] = 0;
				}
			}
		}
		
		
	}
	//dfs수행. 얼음의 크기가 1이상이면 탐색
	public static void dfs(int y,int x) {
		count++;
		dfsVisited[y][x] = true;
		for(int i=0;i<4;i++) {
			int nextY=y+dy[i];
			int nextX=x+dx[i];
			
			if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
				continue;
			if(dfsVisited[nextY][nextX]||map[nextY][nextX]==0)
				continue;
			
			dfs(nextY,nextX);
			
		}
		
	}
	//얼음의 크기의 합계를 구하는 메소드
	public static int calMax() {
		int sum = 0;
	
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map.length;j++) {
				sum+=map[i][j];
			}
		}
		return sum;
		
		
	}

	//2^L 개 크기만큼의 배열을 뒤집는 메소드
	public static void spin(int L) {
		int copy[][]=new int[map.length][map.length];
	
		//해당 크기에 저장된 가장 왼쪽 위를 기준으로 함
		for(int q=0;q<list[L].size();q++){
			
			Integer temp[]= list[L].get(q);
			int y = temp[0];
			int x = temp[1];
			int idx1=0;
			int size= (int) Math.pow(2,L);
			for(int i=0;i<size;i++) {
				int idx2=0;
				for(int j=size-1;j>=0;j--) {
					copy[y+idx1][x+idx2] = map[y+j][x+i]; 
					idx2++;
				}
				idx1++;
			}
			
		}
		
		for(int i=0;i<copy.length;i++) {
			for(int j=0;j<copy.length;j++) {
				map[i][j] = copy[i][j];
			}
		}
		
	}
	//해당 크기로 맵의 구역을 나눔
	public static void divide(int y,int x, int size,int L) {
		int now = (int) Math.pow(2,L);
		//탐색 성공했다면, 해당 크기의 list에 저장
		if(size==now) {
			list[L].add(new Integer[] {y,x});
			return;
		}
		int newSize = size / 2;
		divide(y,x,newSize,L);
		divide(y+newSize,x,newSize,L);
		divide(y,x+newSize,newSize,L);
		divide(y+newSize,x+newSize,newSize,L);

	}

}

5. 결과

472ms 는 처음에 제출한 코드
528ms 는 궁금해서 이미 분할정복을 통해서 구해진 것을 재활용하는 것이 아닌, 파이어스톰이 Q번 수행될때마다 무조건 분할정복으로 해당 구역을 구하도록 설계해서 풀어봤는데, 놀랍게도 크게 차이가 안났다.
N의 크기가 최대 6으로 작아서 그런가 ..?

6. 회고

주석과 보기 편하게 하려고 중간중간 줄 띄어쓰기를 많이 했어도 다 줄여도 120줄 정도 되는 코드인 것 같은데 1시간 만에 풀었다.
역시 구현 문제는 많이 풀어보는게 짱이다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212