https://www.acmicpc.net/problem/19236
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
이 문제의 핵심은 배열을 두개를 쓰는 것이다.
int map[4][4];
여기에는 물고기 번호를 넣는다.
그리고 map이 바뀌면 swap 시키게 된다.
0은 빈 칸, -1은 상어가 있는 칸.
|
1
2
3
4
5
6
7
|
struct info
{
int row;
int col;
int dir;
bool live;
};
|
cs |
info fish[20];
물고기가 1번부터 순서대로 이동을 해서
처음에는 sorting을 했지만
그렇게 하면 시간이 너무 오래걸린다.
index를 물고기 번호로 쓰면
sort를 할 필요가 없다.
4×4크기의 공간
상어와 물고기의 이동에 따른 최댓값을 구하는 문제.
브루트포스(재귀)를 이용한다.
브루트포스 이므로 map을 바꿨으면
map을 다시 바꿔줘야한다.
크기가 크면 맵 복사를 하면 안되지만
4x4 밖에 되지 않으므로 맵 복사를 하자.
4x4라는 크기가 고정되어 있으므로
상어가 갈 수 있는 케이스는
for (int i = 1; i <= 3; i++)
int nx = x + dx[dir] * i;
int ny = y + dy[dir] * i;
이렇게 나타낼 수 있다.
|
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
|
copy_state(c_map, map, c_fish, fish);
move_fish();
// 상어
for (int i = 1; i <= 3; i++)
{
int nx = x + dx[dir] * i;
int ny = y + dy[dir] * i;
if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4)
{
if (map[nx][ny] == 0)
continue;
int fish_num = map[nx][ny];
int n_dir = fish[fish_num].dir;
make_state(x, y, nx, ny, fish_num, true);
go(nx, ny, n_dir, hap + fish_num);
make_state(x, y, nx, ny, fish_num, false);
}
else
break;
}
copy_state(map, c_map, fish, c_fish);
|
cs |
<소스 코드>
|
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int dx[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int ans;
int map[4][4];
struct info
{
int row;
int col;
int dir;
bool live;
};
// 물고기는 최대 16개
info fish[20];
void swap_fish(int idx, int iidx)
{
// swap은 tmp를 써야함
info tmp = fish[idx];
fish[idx].row = fish[iidx].row;
fish[idx].col = fish[iidx].col;
fish[iidx].row = tmp.row;
fish[iidx].col = tmp.col;
}
// 물고기는 1번부터 16번까지 순서대로 움직인다
void move_fish()
{
for (int i = 1; i <= 16; i++)
{
if (fish[i].live == false)
continue;
int x = fish[i].row;
int y = fish[i].col;
int bang = fish[i].dir;
// 자기 방향으로 돌아오면 끝내야 함
int cnt = 1;
while (true)
{
// 자기 방향으로 돌아옴
if (cnt == 9)
break;
int nx = x + dx[bang];
int ny = y + dy[bang];
if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && map[nx][ny] != -1)
{
if (map[nx][ny] == 0)
{
fish[i].row = nx;
fish[i].col = ny;
map[nx][ny] = i;
map[x][y] = 0;
fish[i].dir = bang;
break;
}
else
{
swap_fish(i, map[nx][ny]);
swap(map[x][y], map[nx][ny]);
fish[i].dir = bang;
break;
}
}
else
{
if (bang == 8)
{
bang = 1;
cnt++;
}
else
{
bang++;
cnt++;
}
}
}
}
}
void make_state(int x, int y, int nx, int ny, int fish_num, bool t)
{
if (t == true)
{
map[x][y] = 0;
map[nx][ny] = -1;
fish[fish_num].live = false;
}
else
{
map[x][y] = -1;
map[nx][ny] = fish_num;
fish[fish_num].live = true;
}
}
// 갈 때까지 가는 종료조건 없는 재귀
void go(int x, int y, int dir, int hap)
{
ans = max(ans, hap);
int c_map[4][4];
info c_fish[20];
// 상태 복사
memcpy(c_map, map, sizeof(map));
memcpy(c_fish, fish, sizeof(fish));
// 물고기 움직임
move_fish();
// 상어
// 4 x 4 크기이므로 최대 3칸 움직임
for (int i = 1; i <= 3; i++)
{
int nx = x + dx[dir] * i;
int ny = y + dy[dir] * i;
if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4)
{
if (map[nx][ny] == 0)
continue;
int fish_num = map[nx][ny];
int n_dir = fish[fish_num].dir;
make_state(x, y, nx, ny, fish_num, true);
go(nx, ny, n_dir, hap + fish_num);
// 켰으면 꺼준다
make_state(x, y, nx, ny, fish_num, false);
}
else
break;
}
// 상태 복구
memcpy(map, c_map, sizeof(map));
memcpy(fish, c_fish, sizeof(fish));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
int x, y;
cin >> x >> y;
map[i][j] = x;
fish[x] = { i, j, y, true };
}
}
// 초기 세팅
int f_num = map[0][0];
int f_dir = fish[f_num].dir;
fish[f_num].live = false;
// 상어 위치는 -1로
map[0][0] = -1;
go(0, 0, f_dir, f_num);
cout << ans << '\n';
return 0;
}
|
cs |
