백준 (BOJ) 20058 마법사 상어와 파이어스톰 bfs, 구현

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

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

 

 

나름? 빡 구현 문제

 

핵심은 bfs가 아니라 돌리는 작업에 대한 구현이다.

 

약간만 잘못 접근해도 이상하게 돌려지는데, 이것만 조심하면 나머진 쉽다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

public class Main {
    static int N, Q, sizeOfMap, iceCount, iceBiggest;
    static int[] L;
    static int[][] map, copyMap;
    static boolean[][] visited;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static ArrayList<point> iceBlock;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        sizeOfMap = 2 << N-1;
        map = new int[sizeOfMap][sizeOfMap];

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

        st = new StringTokenizer(br.readLine());
        L = new int[Q];
        for(int i=0; i<Q; ++i){
            L[i] = Integer.parseInt(st.nextToken());
        }
//        for(int i=0; i<sizeOfMap; ++i){
//            for(int j=0; j<sizeOfMap; ++j){
//                System.out.print(map[i][j] + " ");
//            }
//            System.out.println();
//        }
//        System.out.println();

        for(int l=0; l<Q; ++l){
            rotate(L[l]);
            visited = new boolean[sizeOfMap][sizeOfMap];
            fireStorm();
        }

        iceBlock = new ArrayList<>();
        iceCount = 0;
        iceBiggest = 0;
        for(int i=0; i<sizeOfMap; ++i){
            for(int j=0; j<sizeOfMap; ++j){
                if(0 < map[i][j]){
                    iceBlock.add(new point(j, i));
                    iceCount += map[i][j];
                }
            }
        }

        visited = new boolean[sizeOfMap][sizeOfMap];
        for(point p : iceBlock){
            if(!visited[p.y][p.x]){
                int rst = findBiggest(p);
                iceBiggest = Math.max(rst, iceBiggest);
            }
        }

        System.out.print(iceCount+"\n"+iceBiggest);



    }
    static void rotate(int l){ // 끝행, 끝열
        // l은 gridSize를 결정짓는 계수
        int gridSize = 1;
        if(0 < l) gridSize = 2 << l-1;

        for(int i=0; i<sizeOfMap; i += gridSize){ // 세로 줄
            for(int j=0; j<sizeOfMap; j += gridSize){ // 가로 줄부터 먼저 쭉 조진다.
                int count = 0;
                for(int k=gridSize; 1 < k; k -= 2){ // 그리드 영역 이하 모두
                    // 우하단 이동
                    int rowPoint = i + count; // y 좌표
                    int colPoint = j + count; // x 좌표
                    ++count;
                    // 와 돌리기 구현 장난 아니네;
                    int[] upVal = new int[k];
                    int[] downVal = new int[k];
                    int[] rightVal = new int[k];
                    int[] leftVal = new int[k];

                    int kMinus1 = k-1;
                    for (int z = 0; z < k; ++z){
                        upVal[z] = map[rowPoint][colPoint + z];
                        rightVal[z] = map[rowPoint + kMinus1 - z][colPoint + kMinus1];
                        downVal[z] = map[rowPoint + kMinus1][colPoint + z];
                        leftVal[z] = map[rowPoint + kMinus1 - z][colPoint];
                    }
                    for(int z=0; z<k; ++z){
                        map[rowPoint + z][colPoint + kMinus1] = upVal[z]; // 상 -> 우
                        map[rowPoint + kMinus1][colPoint + z] = rightVal[z]; // 우 -> 하
                        map[rowPoint + z][colPoint] = downVal[z]; // 하 -> 좌
                        map[rowPoint][colPoint + z] = leftVal[z];// 좌 -> 상
                    }
                }
            }
        }
    }

    static void fireStorm(){
        copyMap = new int[sizeOfMap][sizeOfMap];
        for(int i=0; i<sizeOfMap; ++i){
            for(int j=0; j<sizeOfMap; ++j) copyMap[i][j] = map[i][j];
        }

        Queue<point> q = new LinkedList<>();
        q.add(new point(0, 0));
        visited[0][0] = true;

        while (!q.isEmpty()){
            point p = q.poll();
            int countMelted = 0; // if > 1, be melted
            for(int i=0; i<4; ++i){
                int nx = dx[i] + p.x;
                int ny = dy[i] + p.y;

                if(-1 < nx && nx < sizeOfMap && -1 < ny && ny < sizeOfMap){
                    if(map[ny][nx] < 1){ // == 얼음이 없을 때, 또한 방문 체크랑 상관 없이 진행해야 한다.
                        ++countMelted;
                    }

                    if(!visited[ny][nx]) { // 얼음인 곳이든 아니든 시점 방문을 하지 않았을 때,
                        visited[ny][nx] = true;
                        q.add(new point(nx, ny)); // 얼음일 때,
                    }
                }
                else ++countMelted;
            }
            if(1 < countMelted){ // 주변에 녹은 지대가 2개 이상일 때,
                --copyMap[p.y][p.x]; // 해당 얼음이 1 줄어든다.
                // break; // 브레이크하면 안 된다.
            }
        }
        for(int i=0; i<sizeOfMap; ++i){
            for(int j=0; j<sizeOfMap; ++j) map[i][j] = copyMap[i][j];
        }
    }

    static int findBiggest(point p){
        Queue<point> q = new LinkedList<>();
        q.add(new point(p.x, p.y));
        visited[p.y][p.x] = true;

        int count = 1;
        while (!q.isEmpty()){
            point pnt = q.poll();

            for(int i=0; i<4; ++i){
                int nx = dx[i] + pnt.x;
                int ny = dy[i] + pnt.y;

                if(-1 < nx && nx < sizeOfMap && -1 < ny && ny < sizeOfMap){
                    if(!visited[ny][nx]){
                        visited[ny][nx] = true;

                        if(0 < map[ny][nx]){ // 얼음이면,
                            ++count;
                            q.add(new point(nx, ny));
                        }
                    }
                }
            }
        }

        return count;
    }

}