문제
접근
뭐랄까 굉장히.. 성가신 구현 문제였다.
일단 상어의 상태를 나타내야하는 변수가 너무 많다..
클래스나 연습해볼겸 클래스로 구현했다.
주어지는 상어의 상태 외에 상어마다 고유 번호를 부여해줬다.(idx)
idx는 나중에 상어끼리 잡아먹을 때 활용할 생각으로 만들었다.
또한 survive 라는 속성을 주어 해당 상어가 잡아먹혔는지 확인하도록 했다.
(그냥 잡아먹혔으면 리스트에서 빼주면 될텐데.. 멍청했다)
대신 survive를 둠으로써 list의 인덱스와 상어의 인덱스가 항상 일치하기 때문에 board에 상어의 인덱스로 표시를 해두면
해당 상어를 찾는데 O(1) 시간이 걸린다는 장점이 있으니 위안으로 삼자.
그리고 board를 하나 두어 현재 상어들의 위치를 표시해두고 낚시꾼이 바로바로 체크하여 잡을 수 있도록 했다.
문제의 흐름은 간단하다.
낚시꾼이 한칸 오른쪽으로 움직인다.
낚시꾼이 서있는 열에서 가장 가까운 상어를 잡는다.
상어들이 움직인다.
이 것을 반복하면 된다.
낚시꾼이 움직이는 건 그냥 for문을 돌면되니 넘어가고,
낚시꾼이 상어를 잡을 차례이다.
killNowColShark()라는 함수를 만들어 구현했다.
동작은 간단하다 현재 열에서 0부터 행의 끝까지 확인한다.
확인하는 칸에 상어가 있고, 그 상어가 살아있다면 상어의 생존 속성을 사망으로 처리한다.
그리고 board에서 해당 칸을 빈칸으로 바꿔주고 죽인 상어의 크기를 반환한다.
이제 상어가 움직일 차례다.(이거 구현한다고 너무 짜증…)
우선 상어가 한 턴에 몇 칸 움직이는지는 speed로 표현된다.
그런데 문제에서 speed의 범위가 1000이라고 한다.
배열의 크기는 최대 100이니까 겹치는게 많을 거다.
우선 제자리로 돌아오기 위해 얼마나 걸리는지 체크해보자.
이 때 제자리는 칸이 같을 뿐아니라, 방향도 같은 것을 의미한다.
그니까 한바퀴돌아서 원위치로 오기 위해선 몇 칸을 움직여야 할까? 가로로 움직이는 것과 세로로 움직이는 건 변수만 다르고 로직은 똑같으니, 세로로 움직이는거로 예를 들자.
높이가 h인 배열에서 현재 x의 위치에 있다.
다시 x로 오기위해선 몇칸 움직여야 할까?
그림은 왠만하면 안그리니까 직접 3~4칸만 그리고 확인해보면 쉽게 공식이 나온다.
(h - 1) * 2 이다.
제자리로 오기 위해서는 h만큼 위로, h만큼 아래로 움직이면 된다.
이 때 h 중에 한자리는 현재 위치니까 h-1을 한다.
그러면 이제 제자리로 돌아오기 위해 필요한 칸의 수를 a라고 하면 전체 speed를 a로 나눈 나머지만 사용해도 결과는 똑같아 진다.
방향전환은 생각보다 간단했다.
상하가 0,1 좌우가 2,3이다.(나는 -1을 해서 그럼)
0,1만 봤을 때 규칙이 바로 보인다.
+1하고 2로 나눈 나머지
이러면 방향이 전환된다.
좌우도 똑같은 방식을 거치고 +2를 해주면 된다.
나는 이걸 따로 함수에 두고 인자에 bias를 받았다.
상하면 0, 좌우면 2 받아서 결과에 더해주면 된다.
그럼 이제 진짜로 상어를 움직여보자.
그냥 한칸씩 움직일까 했다가, 이왕하는거 효율적으로 해보자 생각하고 짯는데, 더 더러워졌다.
현재 위치에서 현재 방향의 끝까지 거리를 d라고 하고, 현재 남은 속도를 speed라고 하자.
그럼 speed가 d보다 크다면 끝점에 도달해서 방향을 전환할 것이다.
그리고 남은 속도는 d를 빼주어야겠지
반대의 경우라면 상어는 현재 위치에서 speed만큼만 이동해주면 된다. 그리고 남은 속도는 0이 되겠지
이걸 남은 속도가 0이 될 때까지 반복하면 잘 움직일 거다.
문제는 방향에 따라 수식이 달라져서 if elif 괴물이 되어버렸다…
어쨋든 이렇게 모든 상어를 움직여 준다.
이 때 상어가 겹치면 잡아먹는다는 조건을 체크해주어야한다.
문제는 특정 상어가 움직였을 때 겹치는 상어가 있다고 하자.
이 겹치는 상어는 움직임을 끝낸 상어일까? 아직 안움직인 상어일까?
모든 상어는 동시에 움직인다고 생각해야 하기 때문에 아직 안움직인 상어는 잡아먹으면 안된다.
하지만 코드상으로는 동시에가 아니고 한 마리씩 움직여주기 때문에 이 부분을 어떻게 체크해야 할까?
방법은 다양할 것이다.
모든 상어를 다 움직인 후에 체크하는 것이 가장 간단한 방법일 거 같다.
하지만 이 방법은 체크를 위해서 board를 전부 다시 확인해야 한다.
나는 아까 처음에 상어에 idx를 부여한 것을 여기서 사용했다.
상어를 움직이는건 idx 순서대로 움직인다.
그럼 현재 상어가 움직였을 때 idx가 더 작은 상어는 이미 움직인 상태이고 idx가 더 큰상어는 아직 움직이지 않은 상태이다.
요걸 이용해서 체크했다.
이동한 위치에 상어가 있는데, 그 상어의 idx가 현재 상어보다 큰 경우 board에 그냥 현재 상어의 idx로 덮어씌워버린다.
문제가 될 것 같지만 별로 상관없다.
상어 클래스에는 최신화된 정보가 정확히 들어있으니 상어 클래스의 속성들로 거의 대부분 체크한다.
코드
- 파이썬 코드
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
import sys
input = sys.stdin.readline
class Shark:
def __init__(self, idx, w, h, speed, d, size):
self.idx = idx
self.width = w
self.height = h
self.speed = speed
self.direction = d
self.size = size
self.survive = 1
def move(self, w, h):
nowSpeed = self.speed
while True:
if self.direction == 0:
distance = self.height
if distance <= nowSpeed:
self.height = 0
self.changeDirection(0)
nowSpeed -= distance
else:
self.height = self.height - nowSpeed
nowSpeed = 0
elif self.direction == 1:
distance = h - self.height - 1
if distance <= nowSpeed:
self.height = h-1
self.changeDirection(0)
nowSpeed -= distance
else:
self.height = self.height + nowSpeed
nowSpeed = 0
elif self.direction == 2:
distance = w - self.width - 1
if distance <= nowSpeed:
self.width = w-1
self.changeDirection(2)
nowSpeed -= distance
else:
self.width = self.width + nowSpeed
nowSpeed = 0
elif self.direction == 3:
distance = self.width
if distance <= nowSpeed:
self.width = 0
self.changeDirection(2)
nowSpeed -= distance
else:
self.width = self.width - nowSpeed
nowSpeed = 0
if nowSpeed == 0:
break
return self.width, self.height
def changeDirection(self, bias):
self.direction = (self.direction + 1) % 2 + bias
def killNowColShark(board, shark, col):
r = len(board)
for i in range(r):
if board[i][col] != -1 and shark[board[i][col]].survive:
killSharkNum = board[i][col]
shark[killSharkNum].survive = 0
board[i][col] = -1
return shark[killSharkNum].size
return 0
def sharkMoveTurn(board, sharkList, w, h):
for shark in sharkList:
if shark.survive == 1:
if board[shark.height][shark.width] == shark.idx:
board[shark.height][shark.width] = -1
noww, nowh = shark.move(w, h)
nowLocVal = board[nowh][noww]
if nowLocVal != -1:
if nowLocVal < shark.idx:
if sharkList[nowLocVal].size < shark.size:
sharkList[nowLocVal].survive = 0
board[nowh][noww] = shark.idx
else:
shark.survive = 0
else:
board[nowh][noww] = shark.idx
else:
board[nowh][noww] = shark.idx
if __name__ == "__main__":
r, c, m = map(int, input().split())
board = [[-1] * c for _ in range(r)]
sharkList = []
for i in range(m):
h, w, speed, direction, size = map(int, input().split())
direction -= 1
h -= 1
w -= 1
# 상하
if direction < 2:
maxMove = (r-1) * 2
# 좌우
else:
maxMove = (c-1) * 2
speed = speed % maxMove
tmp = Shark(i, w, h, speed, direction, size)
board[h][w] = i
sharkList.append(tmp)
answer = 0
for i in range(c):
answer += killNowColShark(board, sharkList, i)
sharkMoveTurn(board, sharkList, c, r)
print(answer)