[백준] 17143번 낚시왕

18500 단어 구현구현

문제 링크

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

문제 설명

  • 낚시왕 x좌표 한 칸씩 이동
  • 이동할 때마다
    • 상어 잡기
    • 상어 이동
      • 구역을 벗어나지 않고 방향을 바꿔서 계속 이동
    • 상어끼리 잡아먹기

풀이

  • board, 상어 리스트 따로 관리
  • 상어 이동
    • 이동 후 위치를 저장할 새로운 board 생성
    • 다음 위치가 구역을 벗어날 경우
      • 이동
    • 벗어나지 않을 경우
      • 끝까지 가서 현재 스피드 감소

코드

def catch(x):
    y = 1
    while y <= r:
        if board[y][x]:
            num = board[y][x][0]
            z = sharks[num][4]
            sharks[num] = []
            board[y][x].pop()
            return z
        y += 1
    return 0


def move():
    global board
    new_board = [[[] for _ in range(c+1)] for _ in range(r+1)]
    for num in range(1, m+1):
        if not sharks[num]:
            continue
        y, x, s, d, z = sharks[num]
        ns = s
        while True:
            ny, nx = y + dy[d] * ns, x + dx[d] * ns
            if 1 <= ny <= r and 1 <= nx <= c:
                new_board[ny][nx].append(num)
                sharks[num] = [ny, nx, s, d, z]
                break
            if d == 1:
                ns = ns - abs(y - 1)
                d = 2
                y = 1
            elif d == 2:
                ns = ns - abs(y - r)
                d = 1
                y = r
            elif d == 3:
                ns = ns - abs(c - x)
                d = 4
                x = c
            elif d == 4:
                ns = ns - abs(x - 1)
                d = 3
                x = 1
    board = new_board


def eat():
    for y in range(1, r+1):
        for x in range(1, c+1):
            if len(board[y][x]) >= 2:
                max_z = float('-inf')
                max_num = -1
                for num in board[y][x]:
                    if max_z < sharks[num][4]:
                        max_z = sharks[num][4]
                        max_num = num
                for num in board[y][x]:
                    if num != max_num:
                        sharks[num] = []
                board[y][x] = [max_num]


# init
import sys
read = sys.stdin.readline
r, c, m = map(int, read().split())
sharks = [[]] + [list(map(int, read().split())) for _ in range(m)]
board = [[[] for _ in range(c+1)] for _ in range(r+1)]
for num in range(1, m+1):
    y, x, s, d, z = sharks[num]
    board[y][x].append(num)
dy, dx = [0,-1,1,0,0], [0,0,0,1,-1]

# start
count = 0
x = 0
while True:
    x += 1
    if x == c+1: 
        break
    count += catch(x)
    move()
    eat()
print(count)

좋은 웹페이지 즐겨찾기