[BOJ] 17143. 낚시왕 (🥇, 시뮬레이션)

🔗

풀이

시뮬레이션 과정은 다음과 같다.

1. 오른쪽으로 한 칸씩 이동한다.
2. 땅과 가장 가까운 상어를 잡는다.
3. 상어가 이동한다

상어는 가야하는 방향으로 이동하다가 격자판에 부딪히게 되면 방향을 반대로 변경하게 된다. 상어의 속도는 1000까지 존재할 수 있는데 격자판 행, 열의 최대 크기는 100이다. 즉, 같은 자리를 계속 오갈 수 있다. 같은 자리를 계속 오가는 경우는 제거하고 핵심 이동거리만 계산할 수 있는 속도만 남겨야 한다.

두 번 튕겨져서 제자리로 돌아오는 경우를 그림으로 표현하면 위와 같다. 전체 행의 길이를 C라고 했을 때 한쪽 끝에서 끝까지 갈 수 있는 이동횟수는 C-1이다. 두 번 튕겨서 제자리에 오기 위해서는 한쪽 끝에서 끝까지 두 번 이동하면 되므로 2x(C-1)만큼의 이동하게 되면 제자리로 돌아오게 된다. 세 번, 네 번 같은 자리를 오고갈 수 있으므로 2x(C-1)을 전체 속도에서 뺀 값이 아니라 나눈 나머지만을 저장한다. 이렇게 되면 이제 제자리로 돌아오는 경우들은 전부 제거하고 아래와 같이 3가지의 방향성을 띌 수 있게 된다.

한 번에 가는 경우

가야하는 속도로 가도 격자판에 닿지 않으므로 방향이 변경되지 않는다. 방향으로 그대로 이동하면 된다.

방향이 한 번 변경되는 경우

격자판에 부딪혀 한 번 튕겨져 방향이 변경되는 경우다. 현재 위치와 격자판까지의 거리만큼을 제외한 거리를 구해서 튕겨져서 어디까지 이동할 수 있는지 위치를 새롭게 구해야 한다. 방향 역시 반대 방향으로 업데이트 해야 한다.

방향이 두 번 변경되는 경우

방향은 두 번 변경되었기 때문에 원래 방향을 그대로 가리키게 된다. 현재 위치에서 이동해야 하는 방향에 있는 격자판까지 이동하는 거리 + 전체 열의 길이를 계산해서 속도에서 제외한 남은 속도만큼을 구해서 두 번째 튕겨진 격자판에서부터 거리를 계산하면 된다.

# 낚시왕

# 땅에 가까운 상어 낚시
def catch(j):
    for i in range(R):
        if arr[i][j]:
            return i
    return -1

# 상어 이동할 위치 찾기
# 3가지 이동 경우에 대해서 각각 처리한다
def find_pos(r, c, s, d, z):
    if d == 1:
        if s<=r:
            r -= s
        elif s<=R-1+r:
            r = s-r 
            d = 2
        else:
            r = R-1-(s-(R-1+r))
    elif d == 2:
        if s<=R-1-r:
            r += s
        elif s<=2*(R-1)-r:
            r = R-1-(s-(R-1-r))
            d = 1
        else:
            r = s-2*(R-1)+r
    elif d == 4:
        if s<=c:
            c -= s
        elif s<=C-1+c:
            c = s-c 
            d = 3
        else:
            c = C-1-(s-(C-1+c))
    elif d == 3:
        if s<=C-1-c:
            c += s
        elif s<=2*(C-1)-c:
            c = C-1-(s-(C-1-c))
            d = 4
        else:
            c = s-2*(C-1)+c
    return r, c, s, d, z

# 상어 이동
def move(arr):
    tmp = [[[] for _ in range(C)] for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if arr[i][j]:
                r, c, s, d, z = find_pos(i, j, *arr[i][j])
                # 만약 상어가 이미 칸에 존재하는데 현재 들어올 상어보다 크기가 더 크다면 그냥 넘어가기
                if tmp[r][c] and tmp[r][c][2] > z:
                    continue
                tmp[r][c] = [s, d, z]
    return tmp

R, C, M = map(int, input().split())
arr = [[[] for _ in range(C)] for _ in range(R)]
for _ in range(M):
    r, c, s, d, z = map(int, input().split())
    if d in (1, 2):
        s %= 2*(R-1)
    else:
        s %= 2*(C-1)
    arr[r-1][c-1] = [s, d, z]

res = 0
for j in range(C):
    i = catch(j)
    if i != -1:
        res += arr[i][j][2]
        arr[i][j] = []
    arr = move(arr)

print(res)