[BOJ] (C++) 20058번: 마법사 상어와 파이어스톰 <Gold 3>

winluck·2024년 1월 28일

BFS C boj 코딩테스트

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

호흡이 길어 실수할 여지가 많았던 문제.

문제 및 입출력

문제에서 추출할 수 있는 정보는 다음과 같다.

N을 입력하면 2^N * 2^N의 격자를 형성한다. (최대 2^6 = 64)
격자별로 시계 방향으로 회전이 일어나며, 이는 테두리 뿐만 아니라 내부도 포함한다.
회전 후 현재 위치 상하좌우를 살피며 얼음이 3개 미만이라면 현재 위치 얼음-1
모든 회전이 끝나고, 남아있는 얼음의 합과 가장 큰 덩어리의 크기를 출력

해결 과정

역시나 삼성답게 해야 할 일이 많다.
이 문제는 크게 4가지로 구성하여 해결하고자 했다.

입력 및 부분 격자 탐색 -> 거듭제곱 및 반복문
부분 격자별 회전 -> 재귀함수
얼음 녹이기 -> 반복문
정답 출력 -> 반복문, DFS/BFS

2번이 가장 핵심적인 부분이었다.

입력 및 부분 격자 탐색

void input(){
    cin >> n >> q;
    len = pow(2, n);
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            cin >> arr[i][j];
        }
    }
}

void solve(){
    int a = 0;
    while(q--){
        cin >> a;
        int s = pow(2, a);
        for(int i=0; i<len; i+=s){ // 부분 격자별 회전
            for(int j=0; j<len; j+=s){
                rotate(i, j, s);
            }
        }
        melt(); // 녹이기
    }
}

s를 통해 단계별 부분 격자의 크기를 저장하고, 전체 격자 기준으로 부분 격자가 차지하는 크기를 고려하여 s만큼 인덱스를 증가시키며 부분 격자의 가장 왼쪽 위 칸을 기준으로 재귀함수를 호출한 뒤, 모든 호출이 끝나면 얼음을 녹인다.

부분 격자별 회전

void rotate(int sx, int sy, int s){

    // 맨 위쪽 배열 임시 저장
    int temp[64] = {0,};
    for(int i=0; i<s; i++){
        temp[i] = arr[sx][sy+i];
    }

    // 왼쪽이 위쪽으로 이동
    for(int i=0; i<s; i++){
        arr[sx][sy+i] = arr[sx+s-1-i][sy];
    }

    // 아래쪽이 왼쪽으로 이동
    for(int i=0; i<s; i++){
        arr[sx+i][sy] = arr[sx+s-1][sy+i];
    }

    // 오른쪽이 아래쪽으로 이동
    for(int i=0; i<s; i++){
        arr[sx+s-1][sy+i] = arr[sx+s-1-i][sy+s-1];
    }

    // 맨 위쪽이 오른쪽으로 이동
    for(int i=0; i<s; i++){
        arr[sx+s-1-i][sy+s-1] = temp[s-1-i];
    }

    // 안쪽으로 이동
    if(s > 2){
        rotate(sx+1, sy+1, s-2);
    }
}

가장 핵심인 회전의 구현이다. 따로 효율적이거나 세련된 방법을 사용하는 것은 실전에서 불가능하다고 생각하여, 직접 한 줄마다 회전을 구현하였다.

먼저 맨 위쪽 라인의 값을 temp 배열로 저장한다.
이후 위쪽 라인을 왼쪽 라인의 값으로 대체하고, 왼쪽은 아래, 아래는 오른쪽, 마지막으로 오른쪽 라인은 아까 저장해둔 temp로 대체한다.

또한, 격자의 테두리 뿐만 아니라 내부 역시 회전이 적용되기 때문에, 재귀함수를 통해 테두리 내부 왼쪽 위 칸을 기준으로 재귀적으로 함수를 호출한다. s가 2인 경우엔 더 이상 호출할 필요가 없다.

얼음 녹이기

void melt(){
    vector<pair<int, int> > v;
    for(int i=0; i<len; i++){ // 녹일 칸 찾기
        for(int j=0; j<len; j++){
            if(arr[i][j] >= 1){
                int cnt = 0;
                for(int a=0; a<4; a++){
                    int nx = i + dx[a];
                    int ny = j + dy[a];
                    if(nx >= 0 && ny >= 0 && nx < len && ny < len){
                        if(arr[nx][ny] >= 1) cnt++;
                    }
                }
                if(cnt < 3) v.push_back(make_pair(i, j));
            }
        }
    }
    for(int i=0; i<v.size(); i++){ // 녹이기
        arr[v[i].first][v[i].second]--;
    }
}

참고로 for문을 순회하며 바로바로 얼음을 녹이는게 아니라, 얼음을 녹일 부분을 정한 뒤 한꺼번에 얼음을 녹여야 한다.

정답 출력

int BFS(int sx, int sy){
    int cnt = 1;
    queue<pair<int, int> > q;
    visited[sx][sy] = true;
    q.push(make_pair(sx, sy));

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= len || ny >= len || visited[nx][ny]) continue;
            if(arr[nx][ny] > 0){
                q.push(make_pair(nx, ny));
                visited[nx][ny] = true;
                cnt++;
            }
        }
    }
    return cnt;
}

void output(){
    // 남아있는 얼음의 합
    int sum = 0;
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            sum += arr[i][j];
        }
    }
    cout << sum << '\n';

    // 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
    int maxsize = 0;
    memset(visited, false, sizeof(visited));
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            if(!visited[i][j] && arr[i][j] >= 1){
                maxsize = max(maxsize, BFS(i, j));
            }
        }
    }
    cout << maxsize << '\n';
}

정답 출력을 위해 BFS를 활용하였다.

소스 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
int n, q;
int len; // 2^n
int arr[64][64];
bool visited[64][64];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

int BFS(int sx, int sy){
    int cnt = 1;
    queue<pair<int, int> > q;
    visited[sx][sy] = true;
    q.push(make_pair(sx, sy));

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= len || ny >= len || visited[nx][ny]) continue;
            if(arr[nx][ny] > 0){
                q.push(make_pair(nx, ny));
                visited[nx][ny] = true;
                cnt++;
            }
        }
    }
    return cnt;
}

void melt(){
    vector<pair<int, int> > v;
    for(int i=0; i<len; i++){ // 녹일 칸 찾기
        for(int j=0; j<len; j++){
            if(arr[i][j] >= 1){
                int cnt = 0;
                for(int a=0; a<4; a++){
                    int nx = i + dx[a];
                    int ny = j + dy[a];
                    if(nx >= 0 && ny >= 0 && nx < len && ny < len){
                        if(arr[nx][ny] >= 1) cnt++;
                    }
                }
                if(cnt < 3) v.push_back(make_pair(i, j));
            }
        }
    }
    for(int i=0; i<v.size(); i++){ // 녹이기
        arr[v[i].first][v[i].second]--;
    }
}

void rotate(int sx, int sy, int s){

    // 맨 위쪽 배열 임시 저장
    int temp[64] = {0,};
    for(int i=0; i<s; i++){
        temp[i] = arr[sx][sy+i];
    }

    // 왼쪽이 위쪽으로 이동
    for(int i=0; i<s; i++){
        arr[sx][sy+i] = arr[sx+s-1-i][sy];
    }

    // 아래쪽이 왼쪽으로 이동
    for(int i=0; i<s; i++){
        arr[sx+i][sy] = arr[sx+s-1][sy+i];
    }

    // 오른쪽이 아래쪽으로 이동
    for(int i=0; i<s; i++){
        arr[sx+s-1][sy+i] = arr[sx+s-1-i][sy+s-1];
    }

    // 맨 위쪽이 오른쪽으로 이동
    for(int i=0; i<s; i++){
        arr[sx+s-1-i][sy+s-1] = temp[s-1-i];
    }

    // 안쪽으로 이동
    if(s > 2){
        rotate(sx+1, sy+1, s-2);
    }
}

void solve(){
    int a = 0;
    while(q--){
        cin >> a;
        int s = pow(2, a);
        for(int i=0; i<len; i+=s){ // 부분 격자별 회전
            for(int j=0; j<len; j+=s){
                rotate(i, j, s);
            }
        }
        melt(); // 녹이기
    }
}

void input(){
    cin >> n >> q;
    len = pow(2, n);
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            cin >> arr[i][j];
        }
    }
}

void output(){
    // 남아있는 얼음의 합
    int sum = 0;
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            sum += arr[i][j];
        }
    }
    cout << sum << '\n';

    // 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
    int maxsize = 0;
    memset(visited, false, sizeof(visited));
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            if(!visited[i][j] && arr[i][j] >= 1){
                maxsize = max(maxsize, BFS(i, j));
            }
        }
    }
    cout << maxsize << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    input();
    solve();
    output();
    return 0;
}

교훈

호흡이 굉장히 길다면 무엇을 해야 하는지 명확하게 단계별로 설정하고, 단계별로 구현하는 것이 좋다.
핵심 로직 구현이 어렵다면 부가적인 로직을 먼저 완성해두는 것도 좋다.

winluck

Discover Tomorrow

이전 포스트

[BOJ] (C++) 20055번: 컨베이어 벨트 위의 로봇 <Gold 5>

다음 포스트