반응형

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

 

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

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 구역을 나눕니다.

 

2. 나눈 구역을 temp 배열에 넣어 90도 회전해줍니다.

 

3. 회전시킨 temp 배열을 arr 배열에 갱신해줍니다.

 

4. 갱신된 arr배열을 바탕으로 temp 배열에 얼음의 양을 갱신해줍니다.

 

5. temp배열을 arr배열에 옮겨 주고 위를 반복합니다.

 

6. 위 과정이 끝나면 arr배열을 바탕으로 ans에 얼음의 양을 저장하고, bfs를 돌려 덩어리의 크기를 Max에 저장합니다.

 

[ 소스코드 ]

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<iostream>
#include<cmath>
#include<queue>
 
using namespace std;
 
int N, Q;
int arr[64][64];
int temp[64][64];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int bfs(int y, int x)    //덩어리 크기
{
    queue<pair<int, int>> q;
    q.push({ y,x });
 
    temp[y][x] = 0;
    int cnt = 1;
 
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if(yy >= 0 && yy < N&& xx >= 0 && xx < N) {
                if (temp[yy][xx] > 0) {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                    cnt++;
                }
            }
        }
    }
 
    return cnt;
}
 
bool check(int y, int x)    //얼음이 주변에 3개 이상 있는지
{
    int cnt = 0;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
 
        if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
            if (arr[yy][xx] > 0) {
                cnt++;
            }
        }
    }
 
    if (cnt >= 3) {
        return true;
    }
    else {
        return false;
    }
}
 
void firestorm()    //파이어스톰 적용
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] > 0) {
                if (!check(i, j)) {
                    temp[i][j] = arr[i][j] - 1;
                }
                else {
                    temp[i][j] = arr[i][j];
                }
            }
            else {
                temp[i][j] = 0;
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            arr[i][j] = temp[i][j];
        }
    }
}
 
void turn(int y, int x, int L)    //90도 회전
{
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < L; j++) {
            temp[i][j] = arr[y + i][x + j];
        }
    }
 
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < L; j++) {
            arr[y + i][x + L - j - 1] = temp[j][i];
        }
    }
}
 
void devide(int L)    //구역 나누기
{
    for (int i = 0; i < N; i += L) {
        for (int j = 0; j < N; j += L) {
            turn(i, j, L);
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    N = pow(2, N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < Q; i++) {
        int L;
        scanf("%d", &L);
        L = pow(2, L);
        devide(L);
 
        firestorm();
    }
 
    int ans = 0;
    int Max = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ans += arr[i][j];
            if (temp[i][j] > 0) {
                int cnt = bfs(i, j);
                Max = max(cnt, Max);
            }
        }
    }
 
    printf("%d\n%d", ans, Max);
}
 
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17822번 - 원판 돌리기 (C++)  (0) 2022.09.25
[ 백준 ] 20057번 - 마법사 상어와 토네이도 (C++)  (0) 2022.09.24
[ 백준 ] 20056번 - 마법사 상어와 파이어볼 (C++)  (0) 2022.09.22
[ 백준 ] 17837번 - 새로운 게임 2 (C++)  (0) 2022.09.21
[ 백준 ] 1107번 - 리모컨 (C++)  (0) 2022.09.20

+ Recent posts

티스토리툴바