코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
문제 이름이
"꼬리잡기놀이"
player만 넣는게 아니라 lane 전부를 넣어야 한다.
int tail[6]; // 각 팀의 플레이어가 몇 명인지 들어간다.
tail이 핵심이다.
이걸 저장 해놓으면 거꾸로 만들 때,
꼬리 물려 있는 상태도 커버가 된다.
1. dfs로 간다.
dfs는 visited를 이용해서 쭈욱 가면 된다.
대가리(1)만 2로 가게 해주면 된다.
map[nx][ny] == 3 이면
tail에 lane[idx].size() 저장
2. player_move()
레인을 다 앞으로 한 칸씩 보내면 된다.
꼬리를 tmp에 저장하고
끝에서 부터 앞으로 하나씩 물리면 된다.
그리고 대가리에 tmp 지정.
3. drawing
player_wichi랑 team_line 그려주기
4. gyaku -> 레인을 돌려버린다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void gyaku(int team_idx)
{
if (team_idx == 0)
return;
vector<pair<int, int>> new_lane;
// 꼬리가 물려있는 거까지 고려 가능
// 거꾸로 넣어준다
for (int i = tail[team_idx] - 1; i >= 0; i--) {
pair<int, int> x = lane[team_idx][i];
new_lane.push_back(x);
}
// 꼬리가 물려 있지 않다면 이 for문을 돌 것이다.
for (int i = (int)lane[team_idx].size() - 1; i >= tail[team_idx]; i--) {
pair<int, int> x = lane[team_idx][i];
new_lane.push_back(x);
}
lane[team_idx] = new_lane;
}
|
cs |
실수들
|
1
2
3
4
5
6
7
8
9
|
// 나머지가 0인 경우도 고려
if (t > (4 * n))
{
int mod = t % (4 * n);
if (mod == 0)
t = 4 * n;
else
t %= (4 * n);
}
|
cs |
if (x == i && y == j)
이거 x == j 되어있었다..
<소스코드>
|
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
|
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, m, turn;
int map[22][22];
int team_line[22][22];
int player_wichi[22][22];
bool visited[22][22];
int ans = 0;
vector<pair<int, int>> lane[6];
// 각 팀의 플레이어 몇 명인지가 들어간다.
int tail[6];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
void dfs(int x, int y, int idx)
{
visited[x][y] = true;
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
{
if (map[nx][ny] != 0 && !visited[nx][ny])
{
// 대가리는 2로 가야함
if ((int)lane[idx].size() == 1 && map[nx][ny] != 2)
continue;
lane[idx].push_back({ nx,ny });
if (map[nx][ny] == 3)
tail[idx] = (int)lane[idx].size();
dfs(nx, ny, idx);
}
}
}
}
void player_move()
{
for (int i = 1; i <= m; i++)
{
// 레인을 다 앞으로 한 칸씩
pair<int, int> tmp = lane[i].back();
for (int j = (int)lane[i].size() - 1; j >= 1; j--)
lane[i][j] = lane[i][j - 1];
lane[i][0] = tmp;
}
}
void drawing()
{
memset(player_wichi, 0, sizeof(player_wichi));
for (int i = 1; i <= m; i++)
{
int soo = 1;
for (int j = 0; j < (int)lane[i].size(); j++)
{
pair<int, int> x = lane[i][j];
if (j <= tail[i] - 1)
player_wichi[x.first][x.second] = soo;
team_line[x.first][x.second] = i;
soo++;
}
}
}
int nageru(int turn)
{
int t = (turn - 1) % (4 * n) + 1;
// 오른쪽
if (t >= 1 && t <= n)
{
for (int j = 1; j <= n; j++)
{
if (player_wichi[t][j] != 0)
{
ans += (player_wichi[t][j] * player_wichi[t][j]);
return team_line[t][j];
}
}
}
// 위
else if (t >= (n + 1) && t <= (2 * n))
{
for (int i = n; i >= 1; i--)
{
if (player_wichi[i][t - n] != 0)
{
ans += (player_wichi[i][t - n] * player_wichi[i][t - n]);
return team_line[i][t - n];
}
}
}
// 왼쪽
else if (t >= (2 * n + 1) && t <= (3 * n))
{
for (int j = n; j >= 1; j--)
{
if (player_wichi[n - (t - 2 * n) + 1][j] != 0)
{
ans += (player_wichi[n - (t - 2 * n) + 1][j] * player_wichi[n - (t - 2 * n) + 1][j]);
return team_line[n - (t - 2 * n) + 1][j];
}
}
}
// 아래
else if (t >= (3 * n + 1) && t <= (4 * n))
{
for (int i = 1; i <= n; i++)
{
if (player_wichi[i][n - (t - 3 * n) + 1] != 0)
{
ans += (player_wichi[i][n - (t - 3 * n) + 1] * player_wichi[i][n - (t - 3 * n) + 1]);
return team_line[i][n - (t - 3 * n) + 1];
}
}
}
// 공을 못받으면 0 반환
return 0;
}
void gyaku(int team_idx)
{
if (team_idx == 0)
return;
vector<pair<int, int>> new_lane;
// 꼬리가 물려있는 거까지 고려 가능
// 거꾸로 넣어준다
for (int i = tail[team_idx] - 1; i >= 0; i--) {
pair<int, int> x = lane[team_idx][i];
new_lane.push_back(x);
}
// 꼬리가 물려 있지 않다면 이 for문을 돌 것이다.
for (int i = (int)lane[team_idx].size() - 1; i >= tail[team_idx]; i--) {
pair<int, int> x = lane[team_idx][i];
new_lane.push_back(x);
}
lane[team_idx] = new_lane;
}
int main()
{
cin >> n >> m >> turn;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cin >> map[i][j];
}
int team_cnt = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
// 대가리를 넣어준다
if (map[i][j] == 1)
lane[team_cnt++].push_back({ i,j });
}
for (int i = 1; i <= m; i++)
dfs(lane[i][0].first, lane[i][0].second, i);
// 이렇게 하면
// lane에 머리부터 꼬리까지 좌표가 들어가있는 상태
for (int t = 1; t <= turn; t++)
{
player_move();
drawing();
int team_idx = nageru(t);
gyaku(team_idx);
}
cout << ans << '\n';
}
|
cs |
