17143 - 낚시왕

이번 문제는 하라는대로 잘 만 하면 되는 문제다.

그러나 딱 한가지 좀 시간이 걸렸던 부분이라면 상어가 더이상 갈 곳이 없으면 반대방향으로 전환하여 계속 남은 부분을 이동하는 것이었는데 분명 수식이 있을것이라 생각하였다. 해당 수식은 sharkMove에 구현되어있다.

이것만 제외하면 생각보다 쉽게 풀려지는 문제였다.

초기

첫번째 이동 후

def sharkMove(x, y, s, d):
    # print("-----------------------" + str(x) + ', ' + str(y) + "-------------------------------")
    # 1 : 위 , 2 : 아래, 3 : 오른쪽, 4 : 왼쪽
    dx = [0, -1, 1, 0, 0]
    dy = [0, 0, 0, 1, -1]
    nx = x + (dx[d] * s); ny = y + (dy[d] * s)
    # print("nx: " + str(nx) + ', ' + 'ny: ' + str(ny))

    # d = 1 = 위, d = 2 = 아래, d = 3 = 오른쪽, d = 4 = 왼쪽
    while nx < 1 or nx > R or ny < 1 or ny > C:
        if nx < 1:
            d = 2
            nx = 1 - (nx-1)
            # print('1 - nx : ' + str(nx))
        elif nx > R:
            d = 1
            nx = (2 * R) - nx
            # print('2 - nx : ' + str(nx))
        elif ny < 1:
            d = 3
            ny = 2 - ny
            # print('3 - ny: ' + str(ny))
        elif ny > C:
            d = 4
            ny = (2 * C) - ny
            # print('4 - ny: ' + str(ny))

    return nx, ny, d

from copy import deepcopy
if __name__ == "__main__":
    # 낚시왕이 있는 곳 = [0,0]

    # 낚시왕이 오른쪽으로 한칸이동
    # 낚시왕이 있는 열의 상어 중에서 땅과 가장 가까운 상어를 잡음 -> 상어는 사라짐
    # 상어 이동

    # 상어가 이동하려는 칸이 격자판의 경계를 넘는 경우에 방향을 바꿔 속력을 유지한채 이동
    # 상어가 이동한 뒤에 한 칸에 상어 두마리 이상이 있을수 있는데, 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹음

    R, C, M = map(int, input().split())
    graph = [[0] * (C + 1) for _ in range(R + 1)]  # 상어 위치
    graph[0][0] = 2  # 낚시꾼의 위치
    sGraph = [[-1] * (C + 1) for _ in range(R + 1)]  # 속력
    dGraph = [[-1] * (C + 1) for _ in range(R + 1)]  # 이동방향
    zGraph = [[-1] * (C + 1) for _ in range(R + 1)]  # 크기
    for i in range(M):
        r, c, s, d, z = map(int, input().split())
        graph[r][c] = 1
        sGraph[r][c] = s
        dGraph[r][c] = d
        zGraph[r][c] = z

    dx = [0, 1, -1, 0, 0]
    dy = [0, 0, 0, 1, -1]

    result = 0
    for c in range(1, C + 1):
        # 낚시꾼의 위치 이동
        graph[0][c - 1] = 0
        graph[0][c] = 2
        # print(zGraph)

        # 낚시왕과 같은 열의 가장 가까운 상어는 잡아먹음
        for r in range(1, R + 1):
            if graph[r][c] == 1:
                result += zGraph[r][c]
                graph[r][c] = 0; sGraph[r][c] = -1; dGraph[r][c] = -1; zGraph[r][c] = -1
                break

        # 상어 이동 확인
        moveChk = [[False] * (C + 1) for _ in range(R + 1)]
        copyGraph = [[0] * (C + 1) for _ in range(R + 1)]; copysGraph = [[-1] * (C + 1) for _ in range(R + 1)]; copydGraph = [[-1] * (C + 1) for _ in range(R + 1)]; copyzGraph = [[-1] * (C + 1) for _ in range(R + 1)]
        for x in range(1, R + 1):
            for y in range(1, C + 1):
                if graph[x][y] == 1:
                    s = sGraph[x][y]
                    d = dGraph[x][y]
                    z = zGraph[x][y]

                    nx, ny, d = sharkMove(x, y, s, d)
                    # 이미 (nx, ny) 좌표에 이동한 물고기가 있음 -> 큰 물고기가 작은 물고기를 잡아먹어야함
                    if moveChk[nx][ny] == True:
                        # 새로 들어오는 상어가 더 큰 경우에 큰 상어의 정보가 바뀌고, 반대의 경우에는 그대로
                        if zGraph[x][y] > copyzGraph[nx][ny]:
                            copysGraph[nx][ny] = sGraph[x][y]
                            copydGraph[nx][ny] = d
                            copyzGraph[nx][ny] = zGraph[x][y]
                    else:
                        moveChk[nx][ny] = True
                        copyGraph[nx][ny] = 1
                        copysGraph[nx][ny] = sGraph[x][y]
                        copydGraph[nx][ny] = d
                        copyzGraph[nx][ny] = zGraph[x][y]

        graph = copyGraph; sGraph = copysGraph; dGraph = copydGraph; zGraph = copyzGraph
    print(result)