[Python] 백준 17143 : 낚시왕

www.acmicpc.net/problem/17143

17143번: 낚시왕

풀이 방법

1. pypy3으로만 통과하는 코드

• 모든 열에 대해 검사해서 가장 가까운 상어의 크기를 answer에 더해준다.
• 낚시 후 모든 상어를 이동한다.
  • 각 상어에 대해 s번 반복문을 돌며 범위에 벗어나면 방향을 바꿔서 이동한다.
• 이렇게 계산하면 시간 복잡도는 아래와 같다.
  
  • 낚시왕이 모든 열에 대해 이동 C * (상어 이동 : RCs) → 100100100*1000 = 1,000,000,000
  • 아슬아슬하게 통과하거나 시간초과

move = [(-1, 0), (1, 0), (0, 1), (0, -1)]
change_dir = [1,0,3,2]
def move_shark(r, c, d, s):
    while s > 0:
        r_ = r+move[d][0]
        c_ = c+move[d][1]
        if 0< r_<=R and 0< c_<=C:
            s -= 1
            r = r_
            c = c_
        else:
            d = change_dir[d]
    return (r, c, d)

R, C, M = map(int, input().split())
shark = [[[] for _ in range (C+1)] for _ in range(R+1)]
for _ in range(M):
    r, c, s, d, z = map(int, input().split())
    shark[r][c] = [s, d-1, z]
answer = 0
for i in range(1, C+1):
    for j in range(1, R+1):
        if shark[j][i]:
            answer += shark[j][i][2]
            shark[j][i] = []
            break
    temp = [[[] for _ in range (C+1)] for _ in range(R+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            if not shark[r][c]: continue
            r_, c_, d_ = move_shark(r, c, shark[r][c][1], shark[r][c][0])
            if temp[r_][c_] and temp[r_][c_][2] > shark[r][c][2]:
                continue
            temp[r_][c_] = shark[r][c]
            temp[r_][c_][1] = d_
    shark = temp
print(answer)

2. python3도 통과하는 코드

• 전체 로직은 동일하지만 상어가 이동할 때 상어마다 s번씩 반복해조면 시간 초과!!
• 상어가 이동하는 코드를 각 상어마다 O(1)로 계산해줘야지 가능하다. (위 코드에서 move_shark부분만 변경)
• 상어 이동 구현 :
  1. 출발지점 (r, c)이 이동하는 방향을 기준으로 끝 지점이 아니라 중앙에서 출발하는 거라면 그 만큼을 s에 더 해준다. 
  2. 왔다갔다 몇 번을 반복해야지 나오는 s인지를 찾고, 짝수번째 방문이라면 방향을 바꾸지 않고, 홀수번째 방문이라면 방향을 바꾼다.
  3. 나머지 만큼 이동
• 사실 상어 이동의 구현은 직접 그려서 규칙성을 찾아야 한다... (글로 표현하기가 힘들다ㅎㅎ) 아래 사진을 참고!

import sys; input = sys.stdin.readline
move = [(-1, 0), (1, 0), (0, 1), (0, -1)]
change_dir = [1,0,3,2]
def move_shark(r, c, d, s):
    if 0 < s * move[d][0] + r <= R and 0 < s * move[d][1] + c <= C:
        return (s * move[d][0] + r, s * move[d][1] + c, d)

    if d == 0:
        s += (R-r)
    elif d == 1:
        s += r-1
    elif d == 2:
        s += c-1
    elif d == 3:
        s += (C - c)

    if d == 2 or d == 3:
        k = (s-1) // (C-1)
        go = (s - k * (C - 1)) % C
    else:
        k = (s-1) // (R-1)
        go = (s - k * (R - 1)) % R
    if k%2 == 1:
        d = change_dir[d]
    if d == 0: r = R
    elif d == 1: r = 1
    elif d == 2: c = 1
    else: c = C
    r += move[d][0]*go
    c += move[d][1]*go
    return (r, c, d)

R, C, M = map(int, input().split())
shark = [[[] for _ in range (C+1)] for _ in range(R+1)]
for _ in range(M):
    r, c, s, d, z = map(int, input().split())
    shark[r][c] = [s, d-1, z]
answer = 0
for i in range(1, C+1):
    for j in range(1, R+1):
        if shark[j][i]:
            answer += shark[j][i][2]
            shark[j][i] = []
            break
    temp = [[[] for _ in range (C+1)] for _ in range(R+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            if not shark[r][c]: continue
            r_, c_, d_ = move_shark(r, c, shark[r][c][1], shark[r][c][0])
            if temp[r_][c_] and temp[r_][c_][2] > shark[r][c][2]:
                continue
            temp[r_][c_] = shark[r][c]
            temp[r_][c_][1] = d_
    shark = temp
print(answer)