백준 - 마법사 상어와 파이어스톰 (C++)

문제 : www.acmicpc.net/problem/20058

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

문제설명

단순 구현 시뮬레이션 문제이다. 배열 회전하는 방법과 BFS를 사용하면 쉽게 풀 수 있다.

알고리즘

1. 배열을 스캔하며 나눠진 구역마다 회전해준다. 회전 방법은 코드에 주석처리 해놨다.

2. 회전 후 인접한 4방향을 탐색하고 조건을 실행한다.

3. 모든 명령을 마친 후 BFS을 통해 가장 큰 덩어리의 개수를 구한다.

주의사항

1. 구역을 나누고 회전하는 부분이 까다로웠는데 작은 배열을 직접 만들고 회전하면서 방법을 찾았다.

구현

#define _CRT_SECURE_NO_WARNINGS 
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>

using namespace std;


int N, Q;
int board[64][64];
int nboard[64][64];
int order[1000];
int val;
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
bool check[64][64];
int ice_sum;
void input()
{
    scanf("%d %d", &N,&Q);
    val = 1;
    for (size_t i = 0; i < N; i++)
    {
        val *= 2;
    }

    for (size_t i = 0; i < val; i++)
    {
        for (size_t j = 0; j < val; j++)
        {
            scanf("%d", &board[i][j]);
        }
    }

    for (size_t i = 0; i < Q; i++)
    {
        scanf("%d", &order[i]);
    }

}


void BFS(int a,int b)
{
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
    check[a][b] = true;
    int cnt = 1;
    while (!q.empty())
    {
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        for (size_t i = 0; i < 4; i++)
        {
            int ny = y+dir[i][0];
            int nx = x + dir[i][1];
            if (ny < val && nx < val && ny > -1 && nx > -1)
            {
                if (!check[ny][nx] && board[ny][nx] > 0)
                {
                    check[ny][nx] = true;
                    q.push(make_pair(ny, nx));
                    cnt++;
                }
            }
        }
    }
    if (cnt > ice_sum)
        ice_sum = cnt;

}



void solve() {

    for (size_t k = 0; k < Q; k++)
    {
        int ord = order[k];
        int ordv = 1;
        memset(nboard, 0, sizeof(nboard)); //한번 돌 때 초기화

        for (size_t i = 0; i < ord; i++) // 구역을 나눈 크기
        {
            ordv *= 2;
        }

        for (int i = 0; i < val; i += ordv)
        {
            for (int j = 0; j < val; j += ordv)
            {
                for (int y = 0; y < ordv; y++)
                {
                    for (int x = 0; x < ordv; x++)
                    {
                        nboard[x + i][ordv - 1 - y + j] = board[y + i][x + j]; // 배열 회전 방법
                    }
                }

            }
        }

        for (size_t i = 0; i < val; i++)
        {
            for (size_t j = 0; j < val; j++)
            {
                board[i][j] = nboard[i][j];
            }
        }

        //주위 얼음 확인하는 부분

        for (size_t i = 0; i < val; i++)
        {
            for (size_t j = 0; j < val; j++)
            {
                int cnt = 0;
                for (size_t c = 0; c < 4; c++)
                {
                    int ny = i + dir[c][0];
                    int nx = j + dir[c][1];

                    if (ny < val && nx < val && ny > -1 && nx > -1)
                    {
                        if (nboard[ny][nx] > 0)
                            cnt++;
                    }
                }
                if (cnt < 3)
                    board[i][j] -= 1;
            }
        }



        /*for (size_t i = 0; i < val; i++)
        {
            for (size_t j = 0; j < val; j++)
            {
                printf("%d ", board[i][j]);
            }
            printf("\n");
        }

        printf("\n");*/
    }

    int sum = 0;
    for (size_t i = 0; i < val; i++)
    {
        for (size_t j = 0; j < val; j++)
        {
            if (board[i][j] > 0)
            {
                sum += board[i][j];
                if (!check[i][j])
                    BFS(i,j);
            }

        }
    }

    printf("%d\n%d", sum,ice_sum);

}

int main() {
    input();
    solve();

}

배운점

배열을 회전하는 방법을 익혔다.