[BOJ][삼성기출] 백준 20058번 - 마법사 상어와 파이어스톰 풀이

| |
백준 온라인 저지 백준 20058번 - 마법사 상어와 파이어스톰 C++ 풀이 (삼성 SW 역량테스트 기출)


문제

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 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)이다.

1

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

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

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


입력

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

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


출력

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


제한

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


풀이

삼성 코딩테스트에서 흔히 등장하는 2차원 배열 안에서의 시뮬레이션 문제이다. 이 문제는 크게 3가지 단계로 나눌 수 있는데 이는 다음과 같다.

  • 격자의 정확한 회전
  • 얼음의 적절한 융해
  • 가장 큰 덩어리 찾기

이 3가지 중에서는 아무래도 격자의 회전이 제일 난이도 있는 구현 파트이다. 격자의 시계/반시계 방향 회전은 자주 출제되는 유형이기 때문에 처음 코드를 짜보고 난 뒤에는 아예 그 코드를 외워두는게 낫다. 구현은 간단하지만 매번 생각해내기에는 시간이 아깝고 충분히 실수가 발생할 수 있기 때문이다.

얼음의 융해는 어려울 점이 없지만 한가지 놓치기 쉬운 부분이 있는데, 바로 얼음이 동시에 융해한다는 것이다. 따라서 2중 for 문을 통해 순차적으로 바로바로 융해시켜주면 안되고, 어느 칸을 융해시킬 지 모든 칸에 대해 미리 정해놓은 다음 일괄적으로 융해시켜야 오류를 범하지 않는다. 미리 융해시켜버린 칸이 0 이 되었을 경우에는 인접한 칸에 영향을 미치기 때문이다.

가장 큰 덩어리 찾기는 일반적인 DFS/BFS 문제이다. 필자는 구현의 간결함을 위해 DFS 로 구현하였다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <cstring>
#define MAX 64
using namespace std;

int N,Q;
int board[MAX][MAX], temp[MAX][MAX];
bool checkMelt[MAX][MAX], visited[MAX][MAX];
const int dy[]={-1,1,0,0};
const int dx[]={0,0,-1,1};

bool inRange(int y,int x){
    return y>=0 && x>=0 && y<N && x<N;
}

int dfs(int y, int x){
    visited[y][x]=true;
    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(inRange(ny,nx) && !visited[ny][nx] && board[ny][nx]>0)
            ret+=dfs(ny,nx);
    }
    return ret;
}

// 가장 큰 덩어리 찾기 - DFS
int getBiggest(){
    int ret=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(board[i][j]>0 && !visited[i][j])
                ret=max(ret,dfs(i,j));
    return ret;
}

// 얼음 합 반환
int getSum(){
    int ret=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            ret+=board[i][j];
    return ret;
}

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

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

    // 모든 격자에 대한 회전
    for(int i=0;i<N;i+=L)
        for(int j=0;j<N;j+=L)
            rotate(i,j,L);

    // 얼음 융해
    memset(checkMelt,false,sizeof(checkMelt));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(board[i][j]==0) continue;
            int cnt=0;
            for(int k=0;k<4;k++){
                int ny=i+dy[k];
                int nx=j+dx[k];
                if(!inRange(ny,nx)) continue;
                if(board[ny][nx]>0) cnt++;
            }
            if(cnt<3) checkMelt[i][j]=true;
        }
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(checkMelt[i][j])
                board[i][j]--;
}

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

    cin>>N>>Q;
    N=(1<<N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin>>board[i][j];

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

    cout<<getSum()<<'\n';
    cout<<getBiggest()<<'\n';

    return 0;
}
0%