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

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)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법을 시전하기 전	L = 1	L = 2

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

출력

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

제한

• 2 ≤ N ≤ 6
• 1 ≤ Q ≤ 1,000
• 0 ≤ A[r][c] ≤ 100
• 0 ≤ Li ≤ N

예제 입력 1 

3 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1

예제 출력 1 

284
64

---

풀이

구현문제이다.. 회전하는게 좀 힘들었던 문제였다.

문제에서 원하는 바를 하나씩 풀이해보겠다.

1. 우리는 Q번 map을 회전하고 얼음을 녹인다.

for(int i=0; i<Q; i++) {
    int L = 1<<Integer.parseInt(st.nextToken());
    map = rotate(L);
    melt();
}

1-1) 2^L 회전

private static int[][] rotate(int l) {
    int[][] tmp = new int[size][size];
    for(int i=0; i<size; i+=l) {
        for(int j=0; j<size; j+=l) {
            for(int x=0; x<l; x++) {
                for(int y=0; y<l; y++) {
                    tmp[i+y][j+l-x-1] = map[i+x][j+y];
                }
            }
        }
    }
    return tmp;
}

1-2) 녹이기

- bfs로 녹일부분을 checked에 찾고 bfs가 종료된 후 녹여주었다.

private static void melt() {
    //LinkedList<Point> meltList = new LinkedList<>();
    boolean[][] checked = new boolean[size][size];
    for(int i=0; i<size; i++) {
        for(int j=0; j<size; j++) {
            if(map[i][j] == 0) continue;
            int cnt = 0;
            for(int k=0; k<4; k++) {
                int nx = i + dist[k][0];
                int ny = j + dist[k][1];
                if(!isIn(nx, ny) || map[nx][ny] == 0) continue;
                cnt++;
            }
            if(cnt < 3) {
                checked[i][j] = true;
            }
        }
    }
    for(int i=0; i<size; i++) {
        for(int j=0; j<size; j++) {
            if(!checked[i][j]) continue;
            map[i][j]--;
            sum--;
        }
    }
}

2. 마지막으로 얼음 덩어리들을 찾으며 얼음의 최대 크기를 갱신한다.

for(int i=0; i<size; i++) {
    for(int j=0; j<size; j++) {
        if(visited[i][j] || map[i][j] == 0) continue;
        iceSize = Math.max(iceSize, findIce(i, j));
    }
}

2-1) 얼음 덩어리를 찾는 함수

private static int findIce(int x, int y) {
    Queue<Point> q = new LinkedList<>();
    q.add(new Point(x, y));
    visited[x][y] = true;
    int iceSize = 0;
    while(!q.isEmpty()) {
        Point now = q.poll();
        iceSize++;

        for(int i=0; i<4; i++) {
            int nx = now.x + dist[i][0];
            int ny = now.y + dist[i][1];

            if(!isIn(nx, ny) || visited[nx][ny] || map[nx][ny] == 0 ) continue;
            visited[nx][ny] = true;
            q.add(new Point(nx, ny));
        }
    }
    return iceSize;
}