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

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

3 10

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 2 0 3 2 1 2 3 2 3

　 

 Output 

248

62

정방행렬을 시계방향으로 90도 회전시키고, 가장 큰 덩어리를 찾기위한 BFS를 구현하여 해결할 수 있습니다.

전체 map[][]의 크기는 2N × 2N 이며, 부분 격자의 크기는 2L × 2L  입니다.

 

① 부분 격자 회전

전체 영역을 탐색하되, 부분 격자 크기만큼 증가하면서 아래와 같이 좌측상단의 좌표를 넘겨줍니다.

넘겨받은 좌표를 기준으로 행렬을 시계방향으로 90도 회전합니다.

※ 기준 좌표가 (0, 0)이 아니라 인자로 전달받은 (x, y)인 것에 유의

 

② 얼을을 주어진 규칙에 따라 녹입니다.

인접한 4 방향에서 얼음이 남아 있는 곳이 3곳 이상이어야 감소하지 않습니다.

처음 주어진 얼음 상태에 따라 추가적으로 얼음이 감소하는 곳도 발생하겠지만

아래와 같이 모서리 4 곳은 인접한 곳이 2곳밖에 없기 때문에 회전 후, 항상 감소할 수 밖에 없습니다.

  

 

   - for문으로 구현 시, 탐색 과정 중간에 얼음의 양을 감소시키면 다른 곳에서 얼음 상태를 잘못 확인하기 때문에

     얼음이 감소하는 곳을 별도로 저장해두고 처리해야 합니다.

 

③ 남아 있는 얼음의 양 구하기

    : 이중 for문을 돌면서 얼음이 남아 있는 곳(map[][] > 0)의 합계를 구합니다.

④ 가장 큰 덩어리 구하기

    - BFS() 혹은 DFS()로 인접한(연결된) 곳을 visited[][] 표시합니다.

    - 한번의 BFS()로 덩어리 크기를 비교 및 갱신합니다.

    * 이때도 마찬가지로 얼음이 남아있지 않은 곳은 연결되지 않은 곳입니다.

 

※ 디버깅 코드

void printState() {
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            printf("%d ", map[x][y]);
        }
        printf("\n");
    }
}

---

#include <stdio.h>
#include <queue>
using namespace std;
inline int max(int A, int B) { return A > B ? A : B; }
const int MAX_N = (1 << 6) + 5;
const int dx[] = {  0, 0, -1, 1 };
const int dy[] = { -1, 1,  0, 0 };
int N, Q, L;
int map[MAX_N][MAX_N], visited[MAX_N][MAX_N];
int target[MAX_N][MAX_N], temp[MAX_N][MAX_N];
struct Node {
    int x, y;
};
queue<Node> que;
 
void rotate(int x, int y, int len) {
    // 회전한 모양을 temp[][]에 저장
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            temp[j][len - 1 - i] = map[x + i][y + j];
        }
    }
 
    // 저장된 temp[][]의 값을 map[][]에 다시 저장
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            map[x + i][y + j] = temp[i][j];
        }
    }
}
 
void rotate() {
    // 부분 격자별 좌측 상단 시작 위치를 찾습니다.
    int len = 1 << L;
    for (int x = 0; x < N; x+=len) {
        for (int y = 0; y < N; y+=len) {
            // 시작 위치(x, y)와 부분격자 크기를 인자로 전달
            rotate(x, y, len);
        }
    }
}
 
void meltIce() {
    for (int x = 0; x < N; ++x) {
        for (int y = 0; y < N; ++y) {
            target[x][y] = 0;
        }
    }
    
    for (int x = 0; x < N; ++x) {
        for (int y = 0; y < N; ++y) {
            int cnt = 0;
            // 인접한 방향 중에서 얼음이 있는지 확인
            for (int i = 0; i < 4; ++i) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];
 
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;
                if (map[nextX][nextY] <= 0) continue;
                cnt++;
            }
            // 3곳 이상 존재하는 경우
            if (cnt < 3) target[x][y] = 1;
        }
    }
 
    // 표시된 곳의 얼음 양 감소
    for (int x = 0; x < N; ++x) {
        for (int y = 0; y < N; ++y) {
            if(target[x][y]) map[x][y]--;
        }
    }
}
 
int sumIce() {
    int ret = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            // 얼음이 남아 있지 않은 부분 제외
            if (map[i][j] <= 0) continue;
            ret += map[i][j];
        }
    }
    return ret;
}
 
int BFS(int x, int y) {
    int ret = 1;
    que.push({ x ,y });
    visited[x][y] = 1;
    while (!que.empty()) {
        Node cur = que.front(); que.pop();
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.x + dx[i];
            int nextY = cur.y + dy[i];
 
            // 범위를 벗어나거나 이미 방문(표시)한 곳, 얼음이 아닌 곳은 제외
            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;
            if (visited[nextX][nextY] || map[nextX][nextY] <= 0) continue;
 
            ret++;
            visited[nextX][nextY] = 1;
            que.push({ nextX, nextY });
        }
    }
    return ret;
}
 
int findLargePiece() {
    int largePiece = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            // 이미 표시되어 있거나 얼음이 아닌 곳은 제외
            if (visited[i][j] || map[i][j] <= 0) continue;
            largePiece = max(largePiece, BFS(i, j));
        }
    }
    return largePiece;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &Q);
    N = 1 << N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d", &map[i][j]);
        }
    }
 
    for (int i = 0; i < Q; ++i) {
        scanf("%d", &L);
        // 부분 격자별 회전
        rotate();
        // 얼음 녹이기
        meltIce();
    }
 
    // 남아 있는 얼음의 양
    printf("%d\n", sumIce()); 
    // 가장 큰 조각의 얼음 공간(개수)
    printf("%d\n", findLargePiece());
}