백준 17143 낚시왕 (파이썬)

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

17143번: 낚시왕

각 상어의 속력만큼 반복문을 돌려서 상어의 좌표를 방향 전환을 포함해 한 칸씩 이동시키면 시간 초과 발생할 수 있다

각 상어의 속력과 방향을 알기 때문에 반복문을 사용하지 않고 조건문으로 한 번에 이동시키도록 구현했다

 

1. 지도를 0으로 초기화하고 입력받은 좌표에 [속력, 방향, 크기] 배열로 저장한다

   상어의 좌표는 q라는 배열에 저장한다 (deque 사용 안함)

2. 낚시할 상어의 좌표를 저장할 rx, ry를 -1로 초기화한다. 초기값이 없으면 반례가 생긴다

   가로로 낚시꾼이 한칸씩 이동하면서 해당 열에서 가장 가까운 상어를 찾는다

   상어가 있으면 해당 좌표를 저장하고 ans에 크기를 더한다

3. q에 있는 상어를 하나씩 꺼내서 이동시킨다. 이 때 rx, ry에 해당하는 상어라면 continue해서 제외한다

4. 상어를 속력만큼 한 번에 이동시킨다. 지도를 벗어나면 주어진 조건대로 움직일 수 있도록 구현한다

5. 지도를 벗어나면 우선 현재 방향에서 지도의 맨 끝으로 이동한다. 속력, 위치, 방향을 잘 신경써야 한다

6. 속력과 행렬에 대한 몫과 나머지를 구한다

7. 몫이 짝수인 경우, 홀수인 경우와 좌표가 0에서 시작하는지 아니면 행렬의 맨끝에서 시작하는지를 고려한다

8. 이동한 좌표에 이미 상어가 있으면 크기를 비교해서 작은 상어를 제거한다

9. 상어가 없으면 큐에 상어의 좌표를 넣어준다

10. 지금까지 잡은 상어의 크기를 출력

import sys

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def dir(d):
    if d == 1: return 2
    elif d == 2: return 1
    elif d == 3: return 4
    else: return 3

r, c, m = map(int, input().split())
a = [[0]*c for _ in range(r)]
q = []

for _ in range(m):
    x, y, s, d, z = map(int, input().split())
    a[x-1][y-1] = [s, d, z]
    q.append([x-1, y-1])

ans, rx, ry = 0, -1, -1
for col in range(c):
    for i in range(r):
        if a[i][col]:
            ans += a[i][col][2]
            a[i][col] = 0
            rx, ry = i, col
            break

    qlen = len(q)
    temp = [[0]*c for _ in range(r)]
    q2 = []
    for i in range(qlen):
        x, y = q[i]
        if x == rx and y == ry:
            continue
        s, d, z = a[x][y][0], a[x][y][1], a[x][y][2]

        if d == 1 or d == 2:
            nx, ny = x + s * dx[d-1], y
            if not 0 <= nx < r:
                temp_s = s
                if d == 1:
                    s -= x
                    x = 0
                else:
                    s -= r-1-x
                    x = r-1
                d = dir(d)
                f, g = s // (r-1), s % (r-1)
                if f % 2 == 0:
                    if x == 0:
                        nx = g
                    else:
                        nx = r-1-g
                else:
                    if x == 0:
                        nx = r-1-g
                    else:
                        nx = g
                    d = dir(d)
                s = temp_s

        else:
            nx, ny = x, y + s * dy[d-1]
            if not 0 <= ny < c:
                temp_s = s
                if d == 3:
                    s -= c-1-y
                    y = c-1
                else:
                    s -= y
                    y = 0
                d = dir(d)
                f, g = s // (c-1), s % (c-1)
                if f % 2 == 0:
                    if y == 0:
                        ny = g
                    else:
                        ny = c-1-g
                else:
                    if y == 0:
                        ny = c-1-g
                    else:
                        ny = g
                    d = dir(d)
                s = temp_s

        if temp[nx][ny]:
            if z > temp[nx][ny][2]:
                temp[nx][ny] = [s, d, z]
        else:
            temp[nx][ny] = [s, d, z]
            q2.append([nx, ny])
    a = temp
    q = q2

print(ans)