[백준] 20058번 : 마법사 상어와 파이어스톰

문제

www.acmicpc.net/problem/20058

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

문제해결방법

이 문제는 단순 구현, BFS를 통해 풀었다.

1. 회전 시킬 배열의 좌측 상단 좌표와 길이를 입력으로 받아서 배열을 회전시키는 rotation이라는 함수를 만들었다.

2. 칸마다 인접한 칸을 확인해서 배열의 칸마다 얼음의 양을 결정하는 check 함수를 만들었다.

3. 위 과정을 통해 마지막 배열을 구하고 BFS를 돌면서 남아있는 얼음의 합과 가장 큰 덩어리의 칸의 개수를 구한다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main20058_마법사상어와파이어스톰 {
 
    public static int N, M, sum, maxCount;
    public static int[][] map;
    
    public static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    public static void check() {
        List<int[]> ice = new ArrayList<>();
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[i].length; j++) {
                if(map[i][j]==0) continue;
                int ch = 0;
                for(int d=0; d<dir.length; d++) {
                    int ii = i+dir[d][0];
                    int jj = j+dir[d][1];
                    if(ii>=0 && ii<N && jj>=0 && jj<N) {
                        if(map[ii][jj]==0) ch++;
                    } else ch++;
                }
                if(ch>1) ice.add(new int[] {i, j});
            }
        }
        for(int[] index : ice) {
            if(map[index[0]][index[1]]==1) map[index[0]][index[1]] = 0;
            else map[index[0]][index[1]]--;
        }
    }
    
    public static void rotation(int i, int j, int length) {
        int[] num = new int[length*length];
        int index = 0;
        for(int x=0; x<length; x++) {
            for(int y=0; y<length; y++) {
                num[index++] = map[i+x][j+y];
            }
        }
        index = 0;
        for(int x=length-1; x>=0; x--) {
            for(int y=0; y<length; y++) {
                map[i+y][j+x] = num[index++];
            }
        }
    }
    
    public static void bfs(int i, int j) {
        int count = 1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {i, j});
        sum += map[i][j];
        map[i][j] = 0;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            for(int d=0; d<dir.length; d++) {
                int ii = cur[0]+dir[d][0];
                int jj = cur[1]+dir[d][1];
                if(ii>=0 && ii<N && jj>=0 && jj<N && map[ii][jj]!=0) {
                    sum += map[ii][jj];
                    map[ii][jj]=0;
                    count++;
                    q.add(new int[] {ii, jj});
                }
            }
        }
        if(maxCount<count) maxCount = count;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        N = (int)Math.pow((double)2, (double)N);
        map = new int[N][N];
        for(int i=0; i<map.length; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<map[i].length; j++) map[i][j] = Integer.parseInt(st.nextToken());
        }
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) {
            int l = Integer.parseInt(st.nextToken());
            l = (int)Math.pow((double)2, (double)l);
            for(int j=0; j<map.length;) {
                for(int k=0; k<map[j].length;) {
                    rotation(j, k, l);
                    k+=l;
                }
                j+=l;
            }
            check();
        }
        sum = 0;
        maxCount = 0;
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[i].length; j++) {
                if(map[i][j]!=0) bfs(i, j);
            }
        }
        System.out.println(sum);
        System.out.println(maxCount);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.