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

문제

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

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

[참고 풀이 링크 : YJYOON`s Code Story]

해당 문제의 풀이 시간이 개인적으로 정했던 기준 시간을 초과하여 풀지 못했으므로 다른 분의 코드를 참고하여 공부하였습니다. 회전하는 함수의 논리와 dfs를 통한 간결한 구현을 배울 수 있는 좋은 풀이라고 생각하였습니다. 해당 코드에 대한 저의 생각을 아래 형식에 맞게 서술하도록 하겠습니다.

 

풀이 과정

1. 격자 사이즈를 기준으로 회전하는 함수 구현

2. 주변의 얼음을 체크하여 얼음이 남아있는 칸이 3칸보다 적다면 해당 칸의 얼음의 수를 줄이는 방식 구현

    (테두리 부분의 얼음이 없기 때문에 얼음이 없는 칸이 없다면 테두리부터 얼음이 녹아들어 간다.)

3. 1-2를 Q번 반복한다.

4. 3번 이후의 상황에서 현재 남은 얼음의 수의 합과 가장 큰 얼음 땅덩어리의 크기를 구한다.(DFS 이용)

 

세부 풀이

(1) rotate 함수

해당 함수를 처음 보고 이렇게 간결하게 구현할 수 있는 동작이었나 라는 생각이 들었다. 해당 함수를 자세히 보게 되면 temp라는 임시 배열의 i, j 위치에 x+L-1-j, y+i의 값을 저장한다. 저장하는 좌표를 나눠서 분석해본다면 열 방향의 증가는 행방 향 감소로 반영, 열 방향 증가는 행방 향 증가로 반영되었다. 이를 그림으로 나타내면 파란색 화살표를 temp, 빨간색 화살표를 board라고 생각하고 표현한 그림은 아래와 같다.

temp에 저장되는 값의 순서는 파란색 화살표 방향이며, board로부터 불러오는 값은 빨간색 화살표 방향이다. 해당 과정을 이해하면 코드의 동작 원리를 이해하는데 도움이 될 것이라고 생각한다.

 

(2) solve 함수

처음 얼음이 녹는 조건을 생각해볼 때 만약 입력 때 얼음이 비어있는 칸이 없다면 얼음이 줄어들지 않는 것 아닌가라고 생각했다. 하지만 모서리 부분은 항상 2개 이하의 얼음에 둘러싸여 있으며 무조건 녹는 상황이며, 테두리의 경우 한쪽면은 무조건 얼음이 없는 상태라 녹기 쉽다. 따라서 해당 과정이 반복된다면 얼음이 비어있는 칸이 없더라도 얼음이 충분히 녹을 수 있다.

 

solve 함수를 통해 rotate를 각 격자의 크기만큼 진행하고, 녹을 얼음을 체크했다. 이렇게 구현한 이유는 녹을 얼음을 미리 녹여버리면 이후 탐색에 영향을 줄 수 있기 때문에 한 번의 탐색을 끝낸 후 다시 탐색하며 반영하는 방식을 이용했다.

 

(3) main 내부

입력을 배열에 저장하지 않고 매 입력마다 solve를 수행하도록 구현하여 메모리를 절약할 수 있었다.

 

(4) dfs 함수 / biggest_ice 함수

인접한 지역의 탐색이라고 생각해 필자는 bfs로 구현을 하려 했었으나, DFS와 visited 배열을 통해 간단하게 구현할 수 있었다. 이 visited 배열은 biggest_ice 함수 내부에서도 사용되며, 만약 이전에 DFS로 탐색이 되었던 칸이라면 이미 이전 경우에 포함되므로 DFS의 중복을 피하여 시간을 절약할 수 있다.

 

 

소스 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N,Q,s;
const int max_n = 64;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int board[max_n][max_n], temp[max_n][max_n];
bool check_melt[max_n][max_n], visited[max_n][max_n];


void Input(){
    cin >> N >> Q;
    s = (1<<N);
    for(int i=0;i<s;i++){
        for(int j=0;j<s;j++){
            cin >> board[i][j];
        }
    }

}

// 격자 시계방향 회전
void rotate(int x, int y, int L){
    for(int i=0;i<L;i++)
        for(int j=0;j<L;j++)
            temp[i][j]=board[x+L-1-j][y+i];
    for(int i=0;i<L;i++)
        for(int j=0;j<L;j++)
            board[x+i][y+j]=temp[i][j];
}


int dfs(int x, int y){
    visited[x][y]=true;
    int ret = 1;
    for(int i=0;i<4;i++){
        int newx = x+dir[i][0];
        int newy = y+dir[i][1];

        if(newx<0 || newx>=s || newy<0 || newy>=s) continue;
        if(visited[newx][newy] || board[newx][newy]==0) continue;
        ret+=dfs(newx, newy);
    }
    return ret;
}


int biggest_ice(){
    int ret=0;
    for(int i=0;i<s;i++){
        for(int j=0;j<s;j++){
            if(board[i][j]>0 && !visited[i][j])
                ret = max(ret,dfs(i,j));
        }
    }
    return ret;
}

int sum_ice(){
    int ret=0;
    for(int i=0;i<s;i++){
        for(int j=0;j<s;j++){
            ret+=board[i][j];
        }
    }

    return ret;
}

void solve(int lq){
    lq = (1<<lq);

    for(int i=0;i<s;i+=lq)
        for(int j=0;j<s;j+=lq)
            rotate(i,j,lq);

    memset(check_melt,false,sizeof(check_melt));
    for(int i=0;i<s;i++){
        for(int j=0;j<s;j++){
            if(board[i][j]==0) continue;
            int cnt=0;
            for(int k=0;k<4;k++){
                int newx = i+dir[k][0];
                int newy = j+dir[k][1];
                if(newx<0 || newx>=s || newy<0 || newy>=s) continue;
                if(board[newx][newy]>0) cnt++;
            }
            if(cnt<3) check_melt[i][j]=true;
        }
    }
    
    for(int i=0;i<s;i++){
        for(int j=0;j<s;j++){
            if(check_melt[i][j])
                board[i][j]--;
        }
    }
}



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    Input();

    while(Q--){
        int lq; cin >>lq;
        solve(lq);
    }

    cout << sum_ice() << '\n';
    cout << biggest_ice() << '\n';
    return 0;
}

 

결과 및 후기

문제를 풀지 못해 아쉬운 생각도 들지만 이번 조사를 통해 배운 점이 많은 것 같아 뿌듯했다.

1. 회전 함수 구현    2. BFS / DFS 관점 확장