17143: 낚시왕

풀이 시간

• 55m
• 무난한 구현 문제. 왜 골드1인지는 모르겠다

구현 방식

• 2차원 리스트(board)에 상어가 있는 좌표마다 상어의 크기를 할당해줌
• 딕셔너리(shark)에 "크기: (속력, 방향)" 형식으로 상어에 대한 정보를 저장해줌

• 전반적인 구현 방식은, C만큼 for문을 돌면서
  1) 현재 열에서 가장 가까운 상어 잡기
  2) 상어 이동
  3) 이동 완료 후 잡아먹기
  를 수행해주면 된다

1. 현재 열에서 가장 가까운 상어 잡기
   -> 그냥 R만큼 for문 돌면서 상어가 있다면 board에서 해당 위치를 0으로 바꾸고 shark에서도 delete 해줌

2. 상어 이동
   -> move_shark(i, j board[i][j]) 함수의 반환값들을 dest_sharks에 저장해둠

3. 이동 완료 후 잡아먹기
   -> dest_sharks 안의 상어를 모두 순회하면서 겹치는 상어가 있다면 크기가 더 큰 상어를 남기고 작은 상어를 없애는 방식으로 처리해줬다

코드

import sys

dx = (-1, 1, 0, 0)
dy = (0, 0, 1, -1)

def move_shark(x, y, size):
    S, d = shark[size]

    board[x][y] = 0
    for s in range(S):
        x += dx[d]; y += dy[d]
        if x == -1:
            d = 1; shark[size] = (S, d)
            x += dx[d] * 2
        elif x == R:
            d = 0; shark[size] = (S, d)
            x += dx[d] * 2
        elif y == -1:
            d = 2; shark[size] = (S, d)
            y += dy[d] * 2
        elif y == C:
            d = 3; shark[size] = (S, d)
            y += dy[d] * 2
    
    return (x, y, size)


R, C, M = map(int, sys.stdin.readline()[:-1].split())
board = [[0] * C for _ in range(R)]
shark = dict() #크기 : (속력, 방향)
for m in range(M):
    r, c, s, d, z = map(int, sys.stdin.readline()[:-1].split()); d -= 1; r -= 1; c -= 1
    board[r][c] = z
    shark[z] = (s, d)

total_size = 0
for c in range(C):
    # 현재 열에서 가장 가까운 상어 잡기
    size = -1
    for r in range(R):
        if board[r][c] != 0:
            size = board[r][c]; board[r][c] = 0
            break
    if size != -1:
        total_size += size
        del shark[size]

    # 상어 이동
    dest_sharks = []
    for i in range(R):
        for j in range(C):
            if board[i][j] != 0:
                dest_sharks.append(move_shark(i, j, board[i][j]))

    # 이동 완료 후 잡아먹기
    for x, y, size in dest_sharks:
        if board[x][y] == 0:
            board[x][y] = size
        else:
            if board[x][y] < size:
                del shark[board[x][y]]
                board[x][y] = size
            else:
                del shark[size]
    
print(total_size)

결과

• 3초 ㅎㅎ.. 최적화는 못시킴