Algorithm 문제
[백준] 17143 - 낚시왕
노예2
2019. 7. 25. 16:52
https://www.acmicpc.net/problem/17143
17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하
www.acmicpc.net
시뮬레이션 유형의 문제.
python dict를 사용해서 상어의 삭제를 구현했다.
상어가 다른 상어를 잡아먹기 때문에, 동일한 칸에 위치하는지는 이동 후의 상어들끼리만 확인하거나 모든 상어가 이동한 후에 확인해야 한다.
|
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
|
import sys
lines = sys.stdin.readlines()
R, C, m = tuple(map(int, lines[0].split()))
dr, dc = [0, -1, 1, 0, 0], [0, 0, 0, 1, -1]
reverse_dir = [0, 2, 1, 4, 3]
sharks = {}
pos = [[-1 for _ in range(C)] for _ in range(R)]
for n, line in enumerate(lines[1:]):
r, c, s, d, z = tuple(map(int, line.split()))
sharks[n] = (r, c, s, d, z)
pos[r-1][c-1] = n
re = 0
for depth in range(R):
if pos[depth][0] != -1:
re += sharks[pos[depth][0]][4]
del sharks[pos[depth][0]]
pos[depth][0] = -1
break
for col in range(1, C):
# move
eaten = []
pos_tmp = [[-1 for _ in range(C)] for _ in range(R)]
for k in sharks.keys():
r, c, s, d, z = sharks[k]
c += (dc[d] * s) % (2 * (C - 1))
r += (dr[d] * s) % (2 * (R - 1))
for _ in range(2):
if c < 1:
c = 2 - c
d = reverse_dir[d]
elif c > C:
c = 2 * C - c
d = reverse_dir[d]
elif r < 1:
r = 2 - r
d = reverse_dir[d]
elif r > R:
r = 2 * R - r
d = reverse_dir[d]
sharks[k] = (r, c, s, d, z)
if pos_tmp[r-1][c-1] != -1:
other = pos_tmp[r-1][c-1]
if z > sharks[other][4]:
eaten.append(other)
pos_tmp[r-1][c-1] = k
else:
eaten.append(k)
else:
pos_tmp[r-1][c-1] = k
for e in eaten:
del sharks[e]
pos = pos_tmp
# catch
for depth in range(R):
if pos[depth][col] != -1:
re += sharks[pos[depth][col]][4]
del sharks[pos[depth][col]]
pos[depth][col] = -1
break
if len(sharks) == 0:
break
sys.stdout.write(str(re))
|
cs |