[backjoon]20058 마법사 상어와 파이어 스톰 java

www.acmicpc.net/problem/20058

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

Gold 4

횟수 갯수 만큼의 단계가 주어지면 그 단계(= 칸수)를 기준으로 회전하고 얼음을 녹인다.

1. 2^n만큼 구역을 나눠주고 그 칸을 회전한다.

2. 전체 탐색하며 얼음을 녹여준다.

3. 1,2를 주어진 단계만큼 수행한다.

4. 제일 큰 덩어리와 얼음의 합을 출력한다.

-> 나의 경우엔 회전과 얼음을 녹이는 부분에서 시간이 많이 걸렸다.

[회전 부분]

public static int[][] tornado(int distance){
		
	int[][] result = new int[n][n];
	//시작점을 잡기 위함	
	for (int startRow = 0; startRow < n; startRow+= distance) {
		for (int startCol = 0; startCol < n; startCol+= distance) {
        	//회전
			for (int i = 0; i < distance; i++) {
				for (int j = 0; j < distance; j++) {
					result[startCol + i][startRow +j] 
                    = ice[startCol + distance -1 -j][startRow+i];
				}
			}
		}
	}
		
	return result;
}

startRow와 startCol은 구역을 나눴을 때 왼쪽 제일 윗부분으로 시작점을 잡아준다.

나눠진 구간내에서 회전시키되, 특정 시작점이 있기에 회전될 위치에 시작점들을 더해준다.

[얼음을 녹이는 부분]

public static void melt() {
	boolean[][] marked = new boolean[n][n];
		
	int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
		
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int cnt = 0;
			if(ice[i][j] == 0) continue;
			for (int dir = 0; dir < 4; dir++) {
				int nextR = i + dirs[dir][0];
				int nextC = j + dirs[dir][1];
					
				if(nextR < 0 || nextC < 0 || nextR >=n || nextC >= n) continue;					
				if(ice[nextR][nextC] <= 0) continue;
				cnt++;
			}
			if(cnt <3) marked[i][j] = true;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if(marked[i][j]) ice[i][j]--;
		}
	}
}

나의 경우에 바로바로 빼주다가 낭패봤다.

얼음을 감소시켜야하는 부분은 꼭 별도로 체크해줘서 하나씩만 감소할 수 있도록 해줘야한다.

 

전체 코드

 

import java.io.*;
import java.util.*;
 
class Main {
    static int n;
    static int[][] ice;
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N =  Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        
        n = 1<< N;// 비트 연산 2의 제곱 연산!
        ice = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int cur = Integer.parseInt(st.nextToken());
                ice[i][j] = cur;
            }
        }
        
        int[] steps = new int[Q];
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < Q; i++) {
            int cur = Integer.parseInt(st.nextToken());
            cur = 1 << cur;
            steps[i] = cur;
            ice = tornado(steps[i]);
            melt();
        }
        
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(ice[i][j] > 0) sum += ice[i][j];
            }
        }
        System.out.println(sum);
        System.out.println(largeOne());
    }
    public static void melt() {
        boolean[][] marked = new boolean[n][n];
        
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int cnt = 0;
                if(ice[i][j] == 0) continue;
                for (int dir = 0; dir < 4; dir++) {
                    int nextR = i + dirs[dir][0];
                    int nextC = j + dirs[dir][1];
                    
                    if(nextR < 0 || nextC < 0 || nextR >=n || nextC >= n) continue;                    
                    if(ice[nextR][nextC] <= 0) continue;
                    cnt++;
                }
                if(cnt <3) marked[i][j] = true;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(marked[i][j]) ice[i][j]--;
            }
        }
    }
    public static int largeOne() {
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        boolean[][] marked = new boolean[n][n];
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(marked[i][j]) continue;
                int cnt = 0;
                Queue<Dot> queue = new LinkedList<Dot>();
                queue.add(new Dot(i, j));
                while(!queue.isEmpty()) {
                    Dot cur = queue.poll();
                    
                    for (int k = 0; k < 4; k++) {
                        int nextR = dirs[k][0] + cur.row;
                        int nextC = dirs[k][1] + cur.col;
                        
                        if(nextR < 0 || nextC < 0 || nextR >=n || nextC >= n) continue;
                        if(marked[nextR][nextC] || ice[nextR][nextC] <= 0) continue;
                        marked[nextR][nextC] = true;
                        cnt++;
                        queue.add(new Dot(nextR, nextC));
                    }
                    
                    result = Math.max(cnt, result);
                    
                }
                
                
            }
        }
        
        return result;
    }
    
    public static int[][] tornado(int distance){
        
        int[][] result = new int[n][n];
        
        for (int startRow = 0; startRow < n; startRow+= distance) {
            for (int startCol = 0; startCol < n; startCol+= distance) {
                for (int i = 0; i < distance; i++) {
                    for(int j = 0; j < distance; j++) {
                        result[startCol + i][startRow +j]=ice[startCol + distance -1 -j][startRow+i];
                    }
                }
            }
        }
        
        return result;
    }
    
}
class Dot{
    int row;
    int col;
    Dot(int r, int c){
        this.row = r;
        this.col = c;
    }
}