코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
23년 하반기는 "연쇄 이동"이었다.
연쇄 이동은 "재귀"로 구현을 한다.
1. 맵을 다시 그려야 한다.
기사의 영역에 기사 번호로 채워진다.
int knight_map[44][44] = { 0, };
초기 기사들의 정보가 주어집니다.
이 정보는 순으로 주어지며,
이는 기사의 처음 위치는 를 좌측 상단 꼭지점으로 하며
세로 길이가 , 가로 길이가 인 직사각형 형태를 띄고 있으며
초기 체력이
생존한 기사들이 총 받은 데미지의 합을 출력 해야하니까
damage도 넣자.
<소스코드>
|
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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
#include <iostream>
#include <cstring>
using namespace std;
// 함정, 빈 칸, 벽
int map[44][44];
int knight_map[44][44] = { 0, };
// 기사가 움직였는가를 알려주는 bool 배열
bool ugoku[32];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int l, n, q;
int ans = 0;
struct k_info
{
int row;
int col;
int height;
int width;
int life;
int damage;
};
k_info knight[33];
// knight_map 그리기
void drawing()
{
memset(knight_map, 0, sizeof(knight_map));
for (int a = 1; a <= n; a++)
{
// 죽었으면 continue
if (knight[a].life <= 0)
continue;
int x = knight[a].row;
int y = knight[a].col;
for (int i = 0; i < knight[a].height; i++)
{
for (int j = 0; j < knight[a].width; j++)
{
knight_map[x + i][y + j] = a;
}
}
}
}
void higai(int idx, int dir)
{
for (int a = 1; a <= n; a++)
{
// 죽었거나, 움직이지 않은 기사거나, 명령을 받은 기사면
if (knight[a].life <= 0 || !ugoku[a] || a == idx)
continue;
int x = knight[a].row;
int y = knight[a].col;
for (int i = 0; i < knight[a].height; i++)
{
for (int j = 0; j < knight[a].width; j++)
{
if (map[x + i][y + j] == 1)
{
knight[a].life -= 1;
knight[a].damage += 1;
}
}
}
}
}
// 연쇄까지 고려한 이동
bool move(int idx, int dir)
{
int x = knight[idx].row;
int y = knight[idx].col;
int row_lim = knight[idx].height;
int col_lim = knight[idx].width;
// 위치 변경
x = x + dx[dir];
y = y + dy[dir];
for (int i = 0; i < row_lim; i++)
{
for (int j = 0; j < col_lim; j++)
{
// 범위를 벗어나거나 벽을 만나면
if (x + i <= 0 || x + i > l || y + j <= 0 || y + j > l || map[x + i][y + j] == 2)
{
return false;
}
// 다른 기사와 충돌
if (knight_map[x + i][y + j] > 0 && knight_map[x + i][y + j] != idx)
{
// 그 기사가 아직 움직이지 않았다면
if (!ugoku[knight_map[x + i][y + j]])
{
ugoku[knight_map[x + i][y + j]] = true;
// 재귀로 들어간다
if (!move(knight_map[x + i][y + j], dir))
return false;
}
}
}
}
return true;
}
// 움직이는 게 가능하면
//ugoku가 true인 기사들의 좌표를 바꿔준다.
void set_wichi(int dir)
{
for (int i = 1; i <= n; i++)
{
if (ugoku[i])
{
knight[i].row += dx[dir];
knight[i].col += dy[dir];
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> l >> n >> q;
for (int i = 1; i <= l; i++)
{
for (int j = 1; j <= l; j++)
{
cin >> map[i][j];
}
}
for (int i = 1; i <= n; i++)
{
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
knight[i].row = a;
knight[i].col = b;
knight[i].height = c;
knight[i].width = d;
knight[i].life = e;
knight[i].damage = 0;
}
for (int a = 1; a <= n; a++)
{
int x = knight[a].row;
int y = knight[a].col;
for (int i = 0; i < knight[a].height; i++)
{
for (int j = 0; j < knight[a].width; j++)
{
knight_map[x + i][y + j] = a;
}
}
}
// 움직일 기사와 방향 지정
for (int i = 0; i < q; i++)
{
int x, y;
cin >> x >> y;
// false로 초기화 해줘야 함
memset(ugoku, false, sizeof(ugoku));
// 이미 사라진 기사 번호도 주어질 수 있다.
if (knight[x].life <= 0)
continue;
bool flag = move(x, y);
ugoku[x] = true;
if (flag)
{
set_wichi(y);
higai(x, y);
drawing();
}
}
for (int i = 1; i <= n; i++)
{
if (knight[i].life <= 0)
continue;
ans += knight[i].damage;
}
cout << ans << '\n';
return 0;
}
|
cs |