https://www.acmicpc.net/problem/17143
17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하
www.acmicpc.net
(수정)
이전의 풀이가 재채점 후에 시간 초과로 바뀌어서 다시 풀었다...
속력 s만큼 이동하면 안되고 결국 똑같은 범위 안에서 왔다 갔다 하는 것이므로 % 연산을 사용하여 이동을 단축시킬 수 있다. 즉 상하로 움직이는 경우에는 (r-1) * 2 , 좌우로 움직이는 경우에는 (c-1) * 2 만큼 움직일 때 원래 자리로 돌아온다.
//상하로 움직이는 경우
if (d <= 2) {
s = s % ((R-1) * 2);
}
else { //좌우로 움직이는 경우
s = s % ((C-1) * 2);
}
s만큼 이동하기 전에 이렇게 추가해줘서 pass하였다.
시뮬레이션 문제인데 상어들이 같은 곳에 있을 때의 처리를 해주는 게 어려웠다.
swea의 미생물 격리(?) 문제랑 살짝 비슷한 것 같다(미생물 격리가 더 어려움)
문제에서 주어지는 상어의 좌표, 속력, 방향, 크기의 정보와 추가적으로 살아있는지 여부를 확인할 bool변수를
구조체로 저장하여 관리하였다.
또한, 배열을 만들어서 상어의 위치에 상어의 인덱스를 저장하였다.(상어의 인덱스는 입력받은 순서다)
예를 들어 두 번째 상어의 좌표가 (1,3)이었다면 map [1][3] = 2
이런 식으로 저장하고 이동하거나 죽으면 다시 0으로 바꿔줬다.
이 배열을 활용하면 낚시왕이 상어를 잡을 때 낚시왕이 서있는 열만 배열에서 쭉 확인해주면 되므로
쉽게 구현할 수 있다.
두 마리 이상의 상어들이 같은 곳에 위치할 때에도 이 배열을 확인하였다.
이동할 좌표에 대해 다음과 같이 나눠서 처리해주었다.
r, c로 이동한다고 가정했을 때,
- map[r][c] = 0 인 경우 ( 다른 상어가 없다)
- 바로 map[r][c]에 현재 상어의 인덱스를 저장하면 된다.
- map[r][c] > i 인 경우 ( 이전 인덱스의 상어가 와 있는 경우 ) // 인덱스 순서대로 진행하지면 동시에 일어나는 일이다!!
- 현재 이동(같은 시간)에서 와 있는 상어이므로 크기를 비교 후 더 큰 상어가 해당 위치에 남아있게 된다.
- map[r][c] < 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
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int R, C, M;
int dx[] = { 0,-1,1,0,0 };
int dy[] = { 0,0,0,1,-1 };
int map[101][101];
struct Shark {
int r;
int c;
int s;
int d;
int z;
//살아있는지 여부
bool isAlive;
};
vector<Shark> vt;
int getShark(int c) {
int getsize = 0;
//낚시왕이 서있는 열의 행들만 검사한다.
for (int i = 1; i <= R; i++) {
//상어가 있으면
if (map[i][c] != 0) {
//크기를 받아오고
getsize = vt[map[i][c]].z;
//잡았으므로 죽인다.
vt[map[i][c]].isAlive = false;
//해당위치에서 지워준다.
map[i][c] = 0;
//가장 가까운 한마리만 잡음로 break
break;
}
}
//크기를 리턴
return getsize;
}
void sharkMove() {
int r, c, s, d, z;
for (int i = 1; i <= M; i++) {
//죽은 상어는 skip
if (vt[i].isAlive == false) continue;
r = vt[i].r;
c = vt[i].c;
s = vt[i].s;
d = vt[i].d;
z = vt[i].z;
//다른 곳으로 이동할 것이므로 원래 있던 자리를 0으로 넣어준다.
//이전 index의 상어가 현재 상어의 자리에 와 있지 않은 경우에만 0으로 초기화
if (map[r][c] == i) {
map[r][c] = 0;
}
//s를 줄여준다.
if (d <= 2) {
s = s % ((R-1) * 2);
}
else {
s = s % ((C-1) * 2);
}
//스피드(s)만큼 d방향으로 이동
for (int j = 0; j < s; j++) {
r += dx[d];
c += dy[d];
//범위를 넘어가는 경우
if (r < 1 || c < 1 || r > R || c > C) {
if (d == 1 || d == 3) {
d += 1;
}
else {
d -= 1;
}
//범위 안으로 하나 들어오고
r += dx[d];
c += dy[d];
//j는 다시 빼준다.(한 번 잘못 움직인 것 이므로)
j--;
}
}
//변경된 좌표와 방향을 상어 정보에 새로 저장
vt[i].r = r;
vt[i].c = c;
vt[i].d = d;
//이동한 곳에 다른 상어가 없다면 바로 저장
if (map[r][c] == 0) {
map[r][c] = i;
}
else if (map[r][c] < i) {
// 이전 인덱스의 상어가 있는 경우에는 크기가 더 큰 상어가 더 작은 상어를 잡아먹는다.
int tmp = vt[map[r][c]].z;
if (z > tmp) {
//현재 인덱스의 상어가 더 큰 경우 원래 있던 상어를 잡아먹는다.
vt[map[r][c]].isAlive = false;
map[r][c] = i;
}
else {
//현재 인덱스의 상어가 더 작은 경우 잡아먹힌다.
vt[i].isAlive = false;
}
}
else {
//현재 인덱스보다 뒷순서의 상어라면 어차피 이동할 것이므로 그냥 덮어쓴다.
map[r][c] = i;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> R >> C >> M;
//상어의 수가 0인 경우는 바로 0을 출력하고 종료
if (M == 0) {
cout << 0 << '\n';
return 0;
}
int r, c, s, d, z;
//index를 1부터 시작해주기 위해서 0번째에 아무거나 넣어놓는다.
vt.push_back({ 0,0,0,0,0 });
for (int i = 1; i <= M; i++) {
cin >> r >> c >> s >> d >> z;
//상어 정보를 벡터에 넣는다.
vt.push_back({ r,c,s,d,z,true });
//배열에 위치한 상어의 index를 저장
map[r][c] = i;
}
int ans = 0;
//C만큼 실행
for (int i = 1; i <= C; i++) {
ans += getShark(i);
sharkMove();
}
cout << ans << "\n";
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 별 찍기 - 10 (0) | 2019.08.31 |
|---|---|
| [BOJ] 1655. 가운데를 말해요 (2) | 2019.08.30 |
| [BOJ] 17406. 배열 돌리기 4 (0) | 2019.08.13 |
| [BOJ] 2468. 안전 영역 (0) | 2019.08.13 |
| [BOJ] 2573. 빙산 (0) | 2019.08.13 |