💡 너비 우선 탐색/깊이 우선 탐색/그래프 이론/그래프 탐색/구현/시뮬레이션
Memory 2060KB Time 84ms Code Length 3712B
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
//1. 모든 부분 격자를 시계 방향으로 90도 회전
//2. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int N, Q;
int iceMap[64][64];
int mapsize;
int schedule[1000];
int TwoN(int num) { // 메모이제이션 하면 더 좋을거같긴함.
int result = 1;
for (int i = 0; i < num; i++) {
result *= 2;
}
return result;
}
void init() {
cin >> N >> Q;
mapsize = TwoN(N);
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
cin >> iceMap[i][j];
}
}
for (int i = 0; i < Q; i++) {
cin >> schedule[i];
}
}
void Rotate(int y, int x, int size) {
int tmp[64][64] = { 0 }; // 옮겨담음
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
tmp[i][j] = iceMap[y + i][x + j];
}
}
for (int i = 0; i < size; i++) { // 회전한 배열 집어넣기
for (int j = 0; j < size; j++) {
iceMap[y + i][x + j] = tmp[size-1-j][i];
}
}
}
void doL(int num) {
int L = num;
int TwoL = TwoN(L);
for (int i = 0; i < mapsize; i += TwoL) {
for (int j = 0; j < mapsize; j += TwoL) {
Rotate(i, j, TwoL);
}
}
}
void iceMelting() {
int tmp[64][64] = { 0 };
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
memset(tmp, 0, sizeof(tmp));
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
if (iceMap[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 (ny >= mapsize || nx >= mapsize || ny < 0 || nx < 0) continue;
if (iceMap[ny][nx] == 0) continue;
cnt++;
}
if (cnt < 3) {
tmp[i][j] = iceMap[i][j] - 1;
}
else {
tmp[i][j] = iceMap[i][j];
}
}
}
memcpy(iceMap, tmp, sizeof(iceMap));
}
void printMap() {
cout << endl;
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
cout << iceMap[i][j] << " ";
}
cout << endl;
}
}
int sumIce() {
int result = 0;
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
result += iceMap[i][j];
}
}
return result;
}
int visited[64][64];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
struct loc{
int y, x;
};
int cntNum(int y ,int x) {
queue<loc> q;
q.push({ y,x });
int result = 1;
while (!q.empty()) {
loc now = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny >= mapsize || nx >= mapsize || ny < 0 || nx < 0) continue;
if (iceMap[ny][nx] == 0) continue; // 얼음 이없다면 안감
if (visited[ny][nx] == 1) continue; // 방문 한곳이라면 안감
visited[ny][nx] = 1;
result++; // 횟수 증가
q.push({ ny,nx });
}
}
return result;
}
int getBiGBolck() {
int result = 0;
memset(visited, 0, sizeof(visited));
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
if (visited[i][j] == 1) continue;
if (iceMap[i][j] > 0) {
visited[i][j] = 1;
int nowcnt = cntNum(i, j);
if (nowcnt > result) { // 가장 큰 덩어리 찾기
result = nowcnt;
}
}
}
}
return result;
}
int main() {
init();
for (int i = 0; i < Q; i++) {
int now = schedule[i];
//1. 모든 부분 격자를 시계 방향으로 90도 회전
if (now != 0) doL(now);
//cout << endl << "after rotate : "<< now << endl;
//printMap();
//2. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다
iceMelting();
//cout << endl<< "after melting" << endl;
//printMap();
}
cout << sumIce() << endl;
cout << getBiGBolck() << endl;
}
모든 부분 격자를 시계 방향으로 90도 회전하는 함수를 구현한다.
주어진 얼음 지도에서, 얼음이 있는 칸 중 3개 또는 그 이상과 인접하지 않은 칸은 얼음의 양을 1 줄인다.
입력을 받고, 주어진 일정대로 격자를 회전하고 얼음을 녹인다.
최종적으로 얼음의 합과 가장 큰 덩어리의 크기를 출력한다.
이 문제에서 실수했던 2가지는 다음과 같다.
- L=1, L=2 그림이 이어지는 줄 알고 L=1에서 L=2로 가는 알고리즘을 작성했다는 것이다. 그것 때문에 구현도 훨씬 어려워지고 머리복잡했는데 L=1과 L=2는 별개였다.. 킹..
- 가장 큰 덩어리가 차지하는 칸의 개수를 출력하라는 부분에서 당연히 가장 큰 덩어리가 가장 얼음의 양이 많은 덩어리를 의미하는 줄 알았다. 이건 문제에서 충분한 오해의 소지가 있다..
고치기 전의 코드는 아래와 같다.
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
//1. 모든 부분 격자를 시계 방향으로 90도 회전
//2. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int N, Q;
int iceMap[64][64];
int mapsize;
int schedule[1000];
int TwoN(int num) { // 메모이제이션 하면 더 좋을거같긴함.
int result = 1;
for (int i = 0; i < num; i++) {
result *= 2;
}
return result;
}
void init() {
cin >> N >> Q;
mapsize = TwoN(N);
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
cin >> iceMap[i][j];
}
}
for (int i = 0; i < Q; i++) {
cin >> schedule[i];
}
}
void Rotate(int y, int x, int size) {
int tmp[64][64] = { 0 }; // 옮겨담음
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
tmp[i][j] = iceMap[y + i][x + j];
}
}
for (int i = 0; i < size; i++) { // 회전한 배열 집어넣기
for (int j = 0; j < size; j++) {
iceMap[y + i][x + j] = tmp[size-1-j][i];
}
}
}
void doL(int num) {
int L = num;
int TwoL = TwoN(L);
for (int i = 0; i < mapsize; i += TwoL) {
for (int j = 0; j < mapsize; j += TwoL) {
Rotate(i, j, TwoL);
}
}
}
void iceMelting() {
int tmp[64][64] = { 0 };
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
memset(tmp, 0, sizeof(tmp));
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
if (iceMap[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 (ny >= mapsize || nx >= mapsize || ny < 0 || nx < 0) continue;
if (iceMap[ny][nx] == 0) continue;
cnt++;
}
if (cnt < 3) {
tmp[i][j] = iceMap[i][j] - 1;
}
else {
tmp[i][j] = iceMap[i][j];
}
}
}
memcpy(iceMap, tmp, sizeof(iceMap));
}
void printMap() {
cout << endl;
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
cout << iceMap[i][j] << " ";
}
cout << endl;
}
}
int sumIce() {
int result = 0;
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
result += iceMap[i][j];
}
}
return result;
}
int visited[64][64];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
struct loc{
int y, x;
};
struct info {
int cnt, size;
};
info cntNum(int y ,int x) {
queue<loc> q;
q.push({ y,x });
info result = {1,iceMap[y][x]};
while (!q.empty()) {
loc now = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny >= mapsize || nx >= mapsize || ny < 0 || nx < 0) continue;
if (iceMap[ny][nx] == 0) continue; // 얼음 이없다면 안감
if (visited[ny][nx] == 1) continue; // 방문 한곳이라면 안감
visited[ny][nx] = 1;
result.cnt++; // 횟수 증가
result.size += iceMap[ny][nx]; // 크기 증가
q.push({ ny,nx });
}
}
return result;
}
int getBiGBolck() {
int result = 0;
int maxsize = 0;
memset(visited, 0, sizeof(visited));
for (int i = 0; i < mapsize; i++) {
for (int j = 0; j < mapsize; j++) {
if (visited[i][j] == 1) continue;
if (iceMap[i][j] > 0) {
visited[i][j] = 1;
info now = cntNum(i, j);
//if (now.cnt == 1) continue; // 덩어리가 아님.
if (now.size > maxsize) { // 가장 큰 덩어리 찾기
maxsize = now.size;
result = now.cnt;
}
}
}
}
return result;
}
int main() {
init();
for (int i = 0; i < Q; i++) {
int now = schedule[i];
//1. 모든 부분 격자를 시계 방향으로 90도 회전
if (now != 0) doL(now);
//cout << endl << "after rotate : "<< now << endl;
//printMap();
//2. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다
iceMelting();
//cout << endl<< "after melting" << endl;
//printMap();
}
cout << sumIce() << endl;
cout << getBiGBolck() << endl;
}
앞으로 문제를 꼼꼼히 읽고 실수를 더 줄여나가야 할 거 같다.
킹 받는 문제 설명..
