파이썬으로 풀어보는 백준 17143번: 낚시왕 (삼성 A형 기출 문제)

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

17143번: 낚시왕

 

 내 풀이:

def move_shark():
    global arr
    next_arr = [[0] * (C+1) for _ in range(R+1)]
    for s in shark:
        if s[4] == 0:
            continue
        if dy[s[3]] * s[2] < 0:
            ny = s[0] + abs((dy[s[3]] * s[2])) % (2 * R - 2) * (-1)
        else:
            ny = s[0] + (dy[s[3]] * s[2]) % (2*R-2)
        if dx[s[3]] * s[2] < 0:
            nx = s[1] + abs((dx[s[3]] * s[2])) % (2 * C - 2) * (-1)
        else:
            nx = s[1] + (dx[s[3]] * s[2]) % (2*C-2)
 
        while True:
            if ny > R:
                ny = R - abs(ny - R)
                s[3] = 1
                continue
            elif ny < 1:
                ny = 1 + abs(ny - 1)
                s[3] = 2
                continue
            if nx > C:
                nx = C - abs(nx - C)
                s[3] = 4
            elif nx < 1:
                nx = 1 + abs(nx - 1)
                s[3] = 3
            else:
                break
 
        if next_arr[ny][nx] > s[4]:
            s[4] = 0
            continue
        elif next_arr[ny][nx] == 0:
            next_arr[ny][nx] = s[4]
            s[0] = ny
            s[1] = nx
        else:
            for eat in shark:
                if eat[4] == next_arr[ny][nx]:
                    eat[4] = 0
                    break
            next_arr[ny][nx] = s[4]
            s[0] = ny
            s[1] = nx
    arr = [next_arr[i][:] for i in range(R + 1)]
 
 
R, C, M = map(int,input().split())
arr = [[0] * (C+1) for _ in range(R+1)]
 
dy = [0, -1, 1, 0, 0]
dx = [0, 0, 0, 1, -1]
 
result = 0
shark = []
for _ in range(M):
    shark.append(list(map(int,input().split())))    # r, c, s, d, z
    arr[shark[_][0]][shark[_][1]] = shark[_][4]
 
for j in range(1, C+1):
    for i in range(1, R+1):
        if arr[i][j] != 0:
            result += arr[i][j]
            for hunt in shark:
                if hunt[4] == arr[i][j]:
                    hunt[4] = 0
                    break
            arr[i][j] = 0
            break
    move_shark()
print(result)

Python3, 4384ms

상어의 정보를 shark 리스트에 저장하고 상어끼리 잡아먹거나 낚시꾼에게 상어가 잡히면 잡힌 상어의 크기를 0으로 바꿔준 다음 크기가 0인 상어는 이동을 하지 않도록 조건문을 세워줬다. 상어가 이동을 하면 그 상어의 좌표값을 변경하였으며 이동한 위치를 저장할 arr를 새로 만들었다. 새로 만든 arr에 이미 상어가 존재하면 이미 존재하는 상어의 크기가 지금 이동할 상어보다 크기가 클 때와 작을 때를 나누어 처리해주었다. 상어의 이동은 상어 정보만 이용해서 처리해줄 수 있었지만 상어 간의 상호작용, 낚시꾼의 처리를 위해 arr를 계속해서 만들고 업데이트를 해야 했다.

 

 

pso999님 풀이:

from sys import stdin
input = stdin.readline
 
def move_fish (R, C, r, c, target, arr):
    s, d, z = target # d - 1: up, 2: down, 3: right, 4: left
    nr, nc, nd = r, c, d
 
    if d == 1: # Up (Row, Negative)
        if s < r:
            nr = r - s
        else:
            nr = (s - r) % (2*R - 2)
            if nr >= R:
                nr = 2*R - 2 - nr
            nd = 2 if int((s - r)/(R - 1)) % 2 == 0 else 1
    elif d == 2: # Down (Row, Positive)
        nr = (r + s) % (2*R - 2)
        if nr >= R:
            nr = 2*R - 2 - nr
        nd = 2 if int((r + s)/(R - 1)) % 2 == 0 else 1
    elif d == 3: # Right (Column, Positive)
        nc = (c + s) % (2*C - 2)
        if nc >= C:
            nc = 2*C - 2 - nc
        nd = 3 if int((c + s)/(C - 1)) % 2 == 0 else 4
    else: # d == 4, Left (Column, Negative)
        if s < c:
            nc = c - s
        else:
            nc = (s - c) % (2*C - 2)
            if nc >= C:
                nc = 2*C - 2 - nc
            nd = 3 if int((s - c)/(C - 1)) % 2 == 0 else 4
 
    if arr[nr][nc] is None or (arr[nr][nc] is not None and arr[nr][nc][2] < z):
        arr[nr][nc] = [s, nd, z]
 
def catch(R, c, arr):
    for r in range(R):
        if arr[r][c] is not None:
            weight = arr[r][c][2]
            arr[r][c] = None
            return weight
    return 0
 
def solution(R, C, M, arr):
    # Move fisher
    weight = 0
    for i in range(C):
        weight += catch(R, i, arr)
 
        # Move fishes
        if i != C - 1:
            next_arr = [[None for _ in range(C)] for _ in range(R)]
            for r in range(R):
                for c in range(C):
                    if arr[r][c] is not None:
                        move_fish(R, C, r, c, arr[r][c], next_arr)
            arr = next_arr
 
    return weight
 
R, C, M = map(int, input().split())
arr = [[None for _ in range(C)] for _ in range(R)]
for i in range(M):
    r, c, s, d, z = map(int, input().split())
    arr[r-1][c-1] = [s, d, z]
 
print(solution(R, C, M, arr))

Python3, 984ms

상어의 이동, 사냥한 상어 처리를 함수로 해결하였다. 내 코드와 4배 정도의 실행 시간 차를 보이는 데 일단 상어 간의 상호 작용을 나보다 쉽게 처리한 것 같다.