[Baekjoon-Python] 17143 : 낚시왕

https://www.acmicpc.net/problem/17143

접근

격자의 열 크기(C)가 5라면 상어가 이동할 때 인덱스(c)는 0, 1, 2, 3, 4, 3, 2, 1, ...이 된다.
상어가 움직일 때 인덱스에 사이클이 발생한다. 사이클 길이는 2 * (C - 1)이다.
상어의 이동 후 인덱스를 중복없이 한 번에 찾도록 최적화해야 시간 초과가 발생하지 않는다.
열, 오른쪽 방향 기준으로 상어의 이동 후 인덱스는 (현재 인덱스 + 속력) % 열 사이클 길이
즉, (c + s) % (2 * (C - 1))이다.

풀이

from sys import stdin


def catch(j):
    for i in range(R): # (1)
        if (i, j) in sharks:
            return sharks.pop((i, j))[2] # (2)
    return 0


def move():
    tmp_sharks = {}
    for (r, c), (s, d, z) in sharks.items():
        nr, nc, d = get_next_location(r, c, s, d) # (3)

        if (nr, nc) in tmp_sharks and tmp_sharks[(nr, nc)][2] > z: # (4)
            continue
        tmp_sharks[(nr, nc)] = (s, d, z) # (5)

    return tmp_sharks


def get_next_location(r, c, s, d):
    if d < 2:
        if d == 0: # (6)
            r = r_cycle - r + s
        else: # (7)
            r += s
        r %= r_cycle
        if r >= R: # (8)
            return r_cycle - r, c, 0
        return r, c, 1
    else:
        if d == 3: # (9)
            c = c_cycle - c + s
        else: # (10)
            c += s
        c %= c_cycle
        if c >= C: # (11)
            return r, c_cycle - c, 3
        return c, s, 2


R, C, M = map(int, stdin.readline().split())
sharks = {}
for _ in range(M):
    r, c, s, d, z = map(int, stdin.readline().split())
    sharks[(r - 1, c - 1)] = (s, d - 1, z)

catch_size = 0
r_cycle = 2 * (R - 1)
c_cycle = 2 * (C - 1)
for j in range(C):
    catch_size += catch(j)
    sharks = move()

print(catch_size)