In [15]:
1
2
3
4
5
6
import sys
from sys import stdin
import numpy as np
sys.path.append("/home/swyoo/algorithm/")
from copy import deepcopy
from utils.verbose import logging_time
17143. 낙시왕
Idea
- 상어 개체를 class로 구현하면 쉽게 접근할 수 있다.
- shift시킨 상태를 보관할
barray를 만들고, grid의 모든 지점에 대해b값을 구하면,
이를 바탕으로 a를 갱신한다.
까다로운 부분:
- 상어의 이동구현
- 상어 객체가 한 격자에 모일 수 있어 이 부분을 처리하기 위해
max([...], key=lambda e: ...)이용. barray를 구하고, 이를 바탕으로a를 갱신하는 것! 주의
In [19]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
stdin = open('data/fishing.txt')
input = stdin.readline
plot = lambda x: print(np.array(x))
R, C, M = list(map(int, input().split()))
class shark:
def __init__(self, s, d, z):
self.s, self.d, self.z = s, d, z
def __repr__(self):
return "({}, {}, {})".format(self.s, self.d, self.z)
a = [[0] * C for _ in range(R)]
for _ in range(M):
r, c, s, d, z = list(map(int, input().split()))
a[r - 1][c - 1] = shark(s, d, z)
delta = {1: (-1, 0), 2: (1, 0), 3: (0, 1), 4: (0, -1)}
del2idx = {v: k for k, v in delta.items()}
plot(a)
1
2
3
4
5
[[0 0 (5, 2, 9) 0 (8, 4, 3) 0]
[0 (2, 3, 5) 0 (8, 4, 1) 0 0]
[0 0 (1, 2, 7) 0 0 (2, 1, 2)]
[(3, 3, 8) 0 0 0 (0, 1, 4) 0]]
Implementation
자세한 설명 및 그림이 필요하다면 여길 방문.
In [23]:
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
@logging_time
def solution(a, show=True):
R, C = len(a), len(a[0])
def shift():
def go(i, j):
x, y, s, (dx, dy) = i, j, a[i][j].s, delta[a[i][j].d]
while s:
if not (0 <= x + dx < R and 0 <= y + dy < C):
dx, dy = -dx, -dy
a[i][j].d = del2idx[(dx, dy)]
x, y = x + dx, y + dy
s -= 1
if b[x][y]:
b[x][y] = max([b[x][y], a[i][j]], key=lambda e: e.z)
else:
b[x][y] = a[i][j]
b = [[0] * C for _ in range(R)]
for i in range(R):
for j in range(C):
if not isinstance(a[i][j], shark): continue
go(i, j)
for i in range(R):
for j in range(C):
a[i][j] = b[i][j]
if show:
print("initial states:")
plot(a)
ans = 0
for j in range(C):
if show: print("{}".format("="*50))
# catch
for i in range(R):
if isinstance(a[i][j], shark):
ans += a[i][j].z
a[i][j] = 0
break
if show:
print("after catching:")
plot(a)
shift()
if show:
print("after shifting:")
plot(a)
return ans
solution(deepcopy(a), show=True, verbose=True)
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
initial states:
[[0 0 (5, 2, 9) 0 (8, 4, 3) 0]
[0 (2, 3, 5) 0 (8, 4, 1) 0 0]
[0 0 (1, 2, 7) 0 0 (2, 1, 2)]
[(3, 3, 8) 0 0 0 (0, 1, 4) 0]]
==================================================
after catching:
[[0 0 (5, 2, 9) 0 (8, 4, 3) 0]
[0 (2, 3, 5) 0 (8, 4, 1) 0 0]
[0 0 (1, 2, 7) 0 0 (2, 1, 2)]
[0 0 0 0 (0, 1, 4) 0]]
after shifting:
[[0 0 0 0 (8, 3, 3) (2, 1, 2)]
[0 0 (5, 1, 9) (2, 3, 5) 0 (8, 3, 1)]
[0 0 0 0 0 0]
[0 0 (1, 2, 7) 0 (0, 1, 4) 0]]
==================================================
after catching:
[[0 0 0 0 (8, 3, 3) (2, 1, 2)]
[0 0 (5, 1, 9) (2, 3, 5) 0 (8, 3, 1)]
[0 0 0 0 0 0]
[0 0 (1, 2, 7) 0 (0, 1, 4) 0]]
after shifting:
[[0 0 (8, 3, 3) 0 0 0]
[0 0 0 (8, 3, 1) 0 (2, 3, 5)]
[0 0 (5, 1, 9) 0 0 (2, 2, 2)]
[0 0 0 0 (0, 1, 4) 0]]
==================================================
after catching:
[[0 0 0 0 0 0]
[0 0 0 (8, 3, 1) 0 (2, 3, 5)]
[0 0 (5, 1, 9) 0 0 (2, 2, 2)]
[0 0 0 0 (0, 1, 4) 0]]
after shifting:
[[0 0 0 0 0 0]
[0 (8, 3, 1) 0 (2, 4, 5) 0 0]
[0 0 0 0 0 (2, 1, 2)]
[0 0 (5, 2, 9) 0 (0, 1, 4) 0]]
==================================================
after catching:
[[0 0 0 0 0 0]
[0 (8, 3, 1) 0 0 0 0]
[0 0 0 0 0 (2, 1, 2)]
[0 0 (5, 2, 9) 0 (0, 1, 4) 0]]
after shifting:
[[0 0 0 0 0 (2, 1, 2)]
[0 (8, 4, 1) 0 0 0 0]
[0 0 (5, 2, 9) 0 0 0]
[0 0 0 0 (0, 1, 4) 0]]
==================================================
after catching:
[[0 0 0 0 0 (2, 1, 2)]
[0 (8, 4, 1) 0 0 0 0]
[0 0 (5, 2, 9) 0 0 0]
[0 0 0 0 0 0]]
after shifting:
[[0 0 0 0 0 0]
[0 0 (5, 2, 9) (8, 4, 1) 0 0]
[0 0 0 0 0 (2, 2, 2)]
[0 0 0 0 0 0]]
==================================================
after catching:
[[0 0 0 0 0 0]
[0 0 (5, 2, 9) (8, 4, 1) 0 0]
[0 0 0 0 0 0]
[0 0 0 0 0 0]]
after shifting:
[[0 0 (5, 1, 9) 0 0 0]
[0 0 0 0 0 (8, 3, 1)]
[0 0 0 0 0 0]
[0 0 0 0 0 0]]
WorkingTime[solution]: 3.29208 ms
1
22
Submitted Code
pypy3는 통과하지만, python은 TLE.
상어들의 움직임을 하나하나씩 iteration하지 말고, 규칙성을 찾아 이용하면 될 것 같다.
In [16]:
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
from sys import stdin
# import numpy as np
stdin = open('data/fishing.txt')
input = stdin.readline
# plot = lambda x: print(np.array(x))
R, C, M = list(map(int, input().split()))
class shark:
def __init__(self, s, d, z):
self.s, self.d, self.z = s, d, z
# def __repr__(self):
# return "({}, {}, {})".format(self.s, self.d, self.z)
a = [[0] * C for _ in range(R)]
for _ in range(M):
r, c, s, d, z = list(map(int, input().split()))
a[r - 1][c - 1] = shark(s, d, z)
delta = {1: (-1, 0), 2: (1, 0), 3: (0, 1), 4: (0, -1)}
del2idx = {v: k for k, v in delta.items()}
def solution(a):
R, C = len(a), len(a[0])
def shift():
def go(i, j):
x, y, s, (dx, dy) = i, j, a[i][j].s, delta[a[i][j].d]
while s:
if not (0 <= x + dx < R and 0 <= y + dy < C):
dx, dy = -dx, -dy
a[i][j].d = del2idx[(dx, dy)]
x, y = x + dx, y + dy
s -= 1
if b[x][y]:
b[x][y] = max([b[x][y], a[i][j]], key=lambda e: e.z)
else:
b[x][y] = a[i][j]
b = [[0] * C for _ in range(R)]
for i in range(R):
for j in range(C):
if not isinstance(a[i][j], shark): continue
go(i, j)
for i in range(R):
for j in range(C):
a[i][j] = b[i][j]
ans = 0
for j in range(C):
# catch
for i in range(R):
if isinstance(a[i][j], shark):
ans += a[i][j].z
a[i][j] = 0
break
shift()
return ans
print(solution(a))
1
2
22
In [None]:
1
Leave a comment