이 문제는 상어가 갈 수 있는 칸 중 어떤 칸을 가느냐에 따라 최댓값이 달라지기 때문에 backtracking을 사용해야 하기 때문에 재귀적인 방법으로 풀어야만 한다.
문제의 아이디어는 바로 떠올랐는데 이를 어떻게 코드화 할지가 쉽게 떠오르지 않아서 시간이 좀 걸렸던 것 같다.
코드
|
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
|
#include<iostream>
#include<vector>
using namespace std;
int dx[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int dy[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int map[5][5];
typedef struct fish
{
int x;
int y;
int dir;
}fish;
fish shark;
fish f[17];
int res;
void dfs(fish f[17], int map[5][5], fish shark, int score)
{
res = max(res, score);
for (int i=1; i<= 16; i++)
{
int x = f[i].x;
int y = f[i].y;
int dir = f[i].dir;
if (dir == -1)
continue;
int flag = 0;
int nx, ny;
int j;
for(j=0; j<8; j++)
{
nx = x + dx[dir];
ny = y + dy[dir];
if (nx <=0 || ny <=0 || nx > 4 || ny > 4)
{
f[i].dir = (dir == 8) ? 1 : dir + 1;
dir = f[i].dir;
continue;
}
if (nx == shark.x && ny == shark.y)
{
f[i].dir = (dir == 8) ? 1 : dir + 1;
dir = f[i].dir;
continue;
}
break;
}
if (j == 8)
continue;
int nidx = map[nx][ny];
if (nidx > 0)
{
f[nidx].x = x;
f[nidx].y = y;
map[x][y] = nidx;
}
else
map[x][y] = 0;
f[i].x = nx;
f[i].y = ny;
map[nx][ny] = i;
} //물고기 이동
int sx = shark.x;
int sy = shark.y;
int sd = shark.dir;
for(int i=1; i<=3; i++)
{
fish tmp[17];
for(int j=1; j<=16; j++)
tmp[j] = f[j];
int tmp_map[5][5];
for(int j=1; j<=4; j++)
for(int k=1; k<=4; k++)
tmp_map[j][k] = map[j][k];
int nx = sx + dx[sd] * i;
int ny = sy + dy[sd] * i;
//map[nx][ny] == 0 물고기가 없는 경우
if (nx <= 0 || ny <= 0 || nx > 4 || ny > 4 || map[nx][ny] == 0)
continue;
shark.x = nx;
shark.y = ny;
int num = tmp_map[nx][ny];
tmp_map[nx][ny] = 0;
shark.dir = tmp[num].dir;
tmp[num].dir = -1;
dfs(tmp, tmp_map, shark, score + num);
}
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
for(int i=1; i<=4; i++)
{
for(int j=1; j<=4; j++)
{
int num;
fish tmp;
cin >> num >> tmp.dir;
tmp.x = i; tmp.y = j;
f[num] = tmp;
map[i][j] = num;
}
}
res = map[1][1];
shark.dir = f[res].dir;
f[res].dir = -1;
shark.x = 1; shark.y = 1;
map[1][1] = 0; //상어
dfs (f, map, shark, res);
cout << res << "\n";
return (0);
}
|
cs |
해당 물고기가 잡혔다는 것을 표시하기 위해 dir에 -1을 넣었고, map상에서 해당 위치에 상어가 있거나 물고기가 없을 경우에 0을 대입하도록 하였다.
재귀로 호출할 다음 변수를 만들어주는 부분이 핵심이었다.
|
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
|
int sx = shark.x;
int sy = shark.y;
int sd = shark.dir;
for(int i=1; i<=3; i++)
{
fish tmp[17];
for(int j=1; j<=16; j++)
tmp[j] = f[j];
int tmp_map[5][5];
for(int j=1; j<=4; j++)
for(int k=1; k<=4; k++)
tmp_map[j][k] = map[j][k];
int nx = sx + dx[sd] * i;
int ny = sy + dy[sd] * i;
//map[nx][ny] == 0 물고기가 없는 경우
if (nx <= 0 || ny <= 0 || nx > 4 || ny > 4 || map[nx][ny] == 0)
continue;
shark.x = nx;
shark.y = ny;
int num = tmp_map[nx][ny];
tmp_map[nx][ny] = 0;
shark.dir = tmp[num].dir;
tmp[num].dir = -1;
dfs(tmp, tmp_map, shark, score + num);
}
|
cs |
물고기의 위치를 저장하고 있는 f의 임시 배열 tmp, 물고기의 번호를 저장하고 있는 map의 임시 배열 tmp_map을 만들어
dfs() 함수의 parameter로 넘겨주게 되면, 항상 tmp와 tmp_map에는 호출된 parameter에 의해 결정되기 때문에
상어가 1칸, 2칸, 3칸을 간 각각의 경우의 map이 기존의 map에 영향을 주지 않은채로 (tmp_map에 저장하여 넘기기 때문에)
상어가 잡을 수 있는 물고기 번호의 최댓값을 계산할 수 있게 되는 것이다.
이러한 방법을 잘 알아놓고 다음에 문제풀 땐 바로 떠올릴 수 있도록 연습해야겠다.
'Study > BOJ' 카테고리의 다른 글
| BOJ - 네트워크 연결(1922) (0) | 2021.04.15 |
|---|---|
| BOJ - 거짓말(1043) (0) | 2021.04.14 |
| BOJ - 최소 스패닝 트리(1197) (0) | 2021.04.14 |
| BOJ - 미네랄(2933) (0) | 2021.04.12 |
| BOJ - 마법사 상어와 파이어스톰(20058) (0) | 2021.04.10 |
