코드
|
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
|
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int N, M, K;
int d[5][2] = {{0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
typedef struct shark
{
int x, y, dir, num;
vector<int> prio[5];
}shark;
typedef struct scent
{
int k, num;
}scent;
int s_num;
scent s[21][21];
int map[21][21];
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> N >> M >> K;
vector<shark> v(M + 1);
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
{
cin >> map[i][j];
if (map[i][j] != 0)
{
shark tmp;
tmp.x = i; tmp.y = j; tmp.num = map[i][j];
v[map[i][j]] = tmp;
}
}
for(int i=1; i<=M; i++)
{
int dir;
cin >> dir;
v[i].dir = dir;
}
for(int i=1; i<=M; i++)
{
for(int k=1; k<=4; k++)
for(int j=0; j<4; j++)
{
int pri;
cin >> pri;
v[i].prio[k].push_back(pri);
}
}
for(int i=1; i<=M; i++)
{
int x = v[i].x;
int y = v[i].y;
scent tmp = {K, v[i].num};
s[x][y] = tmp;
}
int time = 0;
int shark_cnt = M;
while(time <= 1000)
{
if (shark_cnt == 1)
{
printf("%d\n", time);
return (0);
}
deque<shark> q;
for(int i=1; i<=M; i++)
{
int x = v[i].x;
int y = v[i].y;
if (x == -1 && y == -1)
continue;
map[x][y] = 0;
int dir = v[i].dir;
int j;
for(j=0; j<4; j++)
{
int n_dir = v[i].prio[dir][j];
int nx = x + d[n_dir][0];
int ny = y + d[n_dir][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= N)
continue;
if (s[nx][ny].k == 0)
{
v[i].x = nx; v[i].y = ny;
v[i].dir = n_dir;
q.push_back(v[i]);
break;
}
}
if (j == 4) //인접한 방향에 갈 곳이 없다면
{
for(int k=0; k<4; k++)
{
int nx = x + d[v[i].prio[dir][k]][0];
int ny = y + d[v[i].prio[dir][k]][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= N)
continue;
if (s[nx][ny].num == i)
{
v[i].x = nx; v[i].y = ny;
v[i].dir = v[i].prio[dir][k];
q.push_back(v[i]);
break;
}
}
}
}
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if (s[i][j].k != 0)
{
(s[i][j].k)--;
if (s[i][j].k == 0)
s[i][j].num = 0;
}
}
}
while (!q.empty())
{
shark f = q.front();
q.pop_front();
int x = f.x; int y = f.y;
if (map[x][y] == 0 || map[x][y] == f.num)
{
map[x][y] = f.num;
s[x][y].k = K; s[x][y].num = f.num;
}
else
{
if (map[x][y] > f.num)
{
v[map[x][y]].x = -1; v[map[x][y]].y = -1;
map[x][y] = f.num;
s[x][y].k = K; s[x][y].num = f.num;
}
else
{
v[f.num].x = -1;
v[f.num].y = -1;
}
shark_cnt--;
}
}
time++;
}
printf("-1\n");
return (0);
}
|
cs |
날 괴롭히던 상어 문제를 드디어 모두 해결하였다. 구현하고 나니 생각보다 단순한 구현 문제였고, 상어들이 동시에 움직여야 한다는 점만 주의하였다면 금방 풀 수 있었을 것이다.
종료조건을 원래는 상어가 들어있는 vector v를 계속해서 확인해서 상어 1만 남았을 경우를 확인하였는데, 이 또한 실행시간에 부담을 줄 수 있기 때문에 상어의 개수를 관리하면서, 상어가 1마리 남았을 때 종료해주면 시간을 좀 더 줄일 수 있다. (사실 0ms까지 줄일 수 있는 것 같은데, 거기까지 최적화하지는 못하였다.)
상어가 보는 방향에 따라 어떤 방향을 먼저 탐색하는지에 대한 우선순위가 주어져서 다른 문제와는 다르게 색달랐고, 나머지 구현은 비슷했다.
scent 배열은 time당 모두 순회하여 1씩 줄여주는 방식으로 구현되어 있는데, 이를 처음에 향기가 들어있는 vector를 따로 관리하여 해당 vector 내의 값만 줄여주려 했는데, 사실 vector에 대해 삽입과 삭제가 많아지면 많아질 수록 더 느리기 때문에 차라리 O(N^2)으로 완전탐색하여 줄여주는 것이 훨씬 좋다.
'Study > BOJ' 카테고리의 다른 글
| BOJ - 사다리 조작(15684) (0) | 2021.04.22 |
|---|---|
| BOJ - 구슬 탈출 2(13460) (0) | 2021.04.21 |
| BOJ - 행성 터널(2887) (0) | 2021.04.15 |
| BOJ - 다리 만들기 2(17472) (0) | 2021.04.15 |
| BOJ - 네트워크 연결(1922) (0) | 2021.04.15 |
