import sys
input = sys.stdin.readline
dr = [1,0,-1,0]
dc = [0,1,0,-1]
R,C,M = map(int,input().split())
ocean = [[0]*C for i in range(R)]
speed,direction,size,co,dead = {},{},{},{},{}
#속도, 방향, 사이즈, 좌표, 죽었는지 알려주는 dict
for num in range(1,M+1):
r,c,s,d,z = map(int,input().split())
ocean[r-1][c-1] = num
co[num] = (r-1,c-1)
speed[num] = s
if d == 1: #방향전환 편의를 위해서
direction[num] = 2
if d == 2:
direction[num] = 0
if d == 3:
direction[num] = 1
if d == 4:
direction[num] = 3
size[num] = z
dead[num] = 0
result = 0
def fish(x): #낚시하는 함수
global result
for i in range(R):
if ocean[i][x]:
num = ocean[i][x]
ocean[i][x] = 0
result += size[num]
dead[num] = 1
return #물고기 있으면 dead 1로 바꿔주고 size만큼 결과값에 추가
def clear(): #움직이기 전 ocean 초기화
global ocean
ocean = [[0]*C for i in range(R)]
def move(num): #상어 움직이는 함수
if dead[num]: #죽었으면 함수종료
return
s = speed[num]
r,c = co[num]
if direction[num]%2==0: #세로로 움직일때
s %= 2*(R-1)
else:
s %= 2*(C-1)
for i in range(s): #속도만큼 방향으로 이동
r1 = r+dr[direction[num]]
c1 = c+dc[direction[num]]
if not (R>r1>=0 and C>c1>=0): #벽을 만나면 방향 반대로 바꿔줌
direction[num] = (direction[num]+2)%4
r1 = r+dr[direction[num]]
c1 = c+dc[direction[num]]
r,c = r1,c1
co[num] = (r,c) #이동한 좌표로 변경
if ocean[r][c]: #이동한 좌표에 상어 있으면 먹음
num1 = ocean[r][c]
if size[num1]>size[num]:
dead[num] = 1
else:
dead[num1] = 1
ocean[r][c] = num
else:
ocean[r][c] = num
for i in range(C):
fish(i)
clear()
for num in range(1,M+1):
move(num)
print(result)문제 읽어보고 "뭐야 너무 쉬운데?" 했다가 왜맞틀만 한시간 넘게한 문제
알고리즘은 간단하다.
1. 상어를 입력순서에 따라 1~M까지 번호를 부여하고 각 물고기들의 특성을 dict에 저장한다.
2. dead dict도 만들어서 상어가 죽었는지 확인
3. 낚시 함수를 실행한다. 낚시한 상어는 dead 체크
4. ocean을 비운다.
5. move함수를 실행, 같은 칸에 상어가 있으면 한마리만 남긴다
처음에는 4번함수를 실행하지 않아서 코드에 오류가 났었다. 같은 칸에 상어가 있으면 상어를 죽이는데 문제는 움직이기 전 상어를 죽였던 것이다. 그래서 바다를 초기화시켜주는 작업이 필요했다.
그 다음에는 시간초과가 문제였는데, 이는 질문게시판에서 힌트를 얻었다. 속도가 매우 빠른 상어가 있는데, 이러면 move함수가 계산을 너무 많이 하는것이 문제였다. 따라서 속도를 가로 혹은 세로길이의 두배로 나눈 나머지값으로 변경해주었다.
그렇게 수정하자 pypy3에서는 통과되었다. 그러나 python3에서는 계속 시간초과가 났다. 시간복잡도를 더 줄일 수 있는 방법을 모색해야겠다.
오늘의 교훈) 다양한 변수를 의식하자