[백준][구현] 낚시왕

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

17143번: 낚시왕

 

내가 작성한 코드

import sys
from collections import defaultdict
_speed = 0
_direction = 1
_size = 2


def deploy_shark(sharks, r, c, speed, direction, size):
    # (1) set if empty || (2) set size if the size is larger
    if not sharks[c][r] or sharks[c][r][_size] < size:
        sharks[c][r] = (speed, direction, size)


def read_data():
    read = sys.stdin.readline
    R, C, M = map(int, read().rstrip().split())
    sharks = defaultdict(lambda: defaultdict(tuple))
    for _ in range(M):
        r, c, speed, direction, size = map(int, read().rstrip().split())
        deploy_shark(sharks, r, c, speed, direction-1, size)
    return R, C, M, sharks


def fishing_shark(sharks, fisher):
    if sharks[fisher]:
        shark = min(sharks[fisher])
        size = sharks[fisher][shark][_size]
        del sharks[fisher][shark]
        return size
    return 0


def change_direction(direction):
    if direction % 2 == 1:
        return direction - 1
    return direction + 1


def shark_up(R, r, speed, direction):
    speed = speed % ((R - 1) * 2)
    if r - speed > 1:
        r = r - speed
    else:
        direction = change_direction(direction)
        r, direction = shark_down(R, 1, speed - (r - 1), direction)
    return r, direction


def shark_down(R, r, speed, direction):
    speed = speed % ((R - 1) * 2)
    if r + speed < R:
        r = r + speed
    else:
        direction = change_direction(direction)
        r, direction = shark_up(R, R, speed - (R - r), direction)
    return r, direction


def shark_left(C, c, speed, direction):
    speed = speed % ((C - 1) * 2)
    if c - speed > 1:
        c = c - speed
    else:
        direction = change_direction(direction)
        c, direction = shark_right(C, 1, speed - (c - 1), direction)
    return c, direction


def shark_right(C, c, speed, direction):
    speed = speed % ((C - 1) * 2)
    if c + speed < C:
        c = c + speed
    else:
        direction = change_direction(direction)
        c, direction = shark_left(C, C, speed - (C - c), direction)
    return c, direction


def shark_move(R, C, r, c, speed, direction):
    # 0=up, 1=down, 2=right, 3=left
    if direction == 0:
        r, direction = shark_up(R, r, speed, direction)
    elif direction == 1:
        r, direction = shark_down(R, r, speed, direction)
    elif direction == 2:
        c, direction = shark_right(C, c, speed, direction)
    else:
        c, direction = shark_left(C, c, speed, direction)

    return r, c, direction


def sharks_move(sharks, R, C):
    nw_sharks = defaultdict(lambda: defaultdict(tuple))

    for c, rs in sharks.items():
        for r in rs:
            speed, direction, size = sharks[c][r]
            nw_r, nw_c, nw_direction = shark_move(R, C, r, c, speed, direction)
            deploy_shark(nw_sharks, nw_r, nw_c, speed, nw_direction, size)

    return nw_sharks

# main
R, C, M, sharks = read_data()
answer = 0
for fisher in range(1, C+1):
    answer += fishing_shark(sharks, fisher)
    sharks = sharks_move(sharks, R, C)
print(answer)

• 상어 위치
  
  • sharks = defaultdict(lambda: defaltdict(tuple))
  • sharks[c][r] = (speed, direction, size)
  • 같은 위치에 상어가 있으면 size를 비교
• 상어 이동
  • 제자리로 오는 경우 : speed를 speed % (R-1) * 2 or speed % (C-1) * 2로 바꿔줌
  • 방향이 그대로인 경우 : r/c를 speed만큼 +/-
  • 방향이 빠뀌는 경우 : (1) r/c를 가장 끝 값으로 이동 (2) direction을 바꿈 (3) 이동한만큼 뺀 speed로 반대방향 이동

 

다른 사람이 작성한 코드

from copy import deepcopy
import sys
sys.stdin = open("input.txt",'r')

R, C, M = map(int,input().split())
board = [[0]*C for _ in range(R)]

for _ in range(M):
    r,c,s,d,z = map(int,input().split())
    board[r-1][c-1] = [s,d,z] #속력, 이동방향, 크기

dir = [[-1,0],[1,0],[0,1],[0,-1]]
# 낚시왕이 오른쪽으로 한 칸 이동한다.
# 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
# 상어가 이동한다.
ans = 0

def outrange(i,j,fast,d):

    dx, dy = dir[d-1]
    if d == 1 or d == 2:
        fast = fast % ((R-1)*2)
    elif d == 3 or d == 4:
        fast = fast % ((C-1)*2)
    while True:
        if -1 < i+dx*fast < R and -1 < j+dy*fast < C:
            return (i+dx*fast, j+dy*fast, d)

        if d == 1:
            fast -= i # 가장 위로 만들어주고
            dx, dy = 1, 0 # 방향 바꿔버리기
            i = 0
            d = 2

        elif d == 2: # 가장 아래로 만들어주고
            fast -= (R-1-i) 
            dx, dy = -1, 0
            i = R-1
            d = 1
        elif d == 3: # 가장 오른쪽으로 만들고
            fast -= (C-1-j)
            dx, dy = 0, -1
            j = C -1
            d = 4
        elif d == 4: # 가장 왼쪽
            fast -= j
            dx, dy = 0, 1
            j = 0
            d = 3
# 상어를 잡는 낚시꾼
for j in range(C):
    for i in range(R):
        if board[i][j] != 0:
            ans += board[i][j][2]
            board[i][j] = 0
            break

    # 상어의 이동
    new_board= [[0]*C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if board[i][j] != 0: # 상어가 있다면
                fast = board[i][j][0]
                nx, ny, d = outrange(i,j,fast,board[i][j][1])
                if new_board[nx][ny] == 0: # 아무도 없을때
                    new_board[nx][ny] = [board[i][j][0],d,board[i][j][2]]

                else: # 있다면 잡아먹으렴...
                    if new_board[nx][ny][2] < board[i][j][2]:
                        new_board[nx][ny] = [board[i][j][0],d,board[i][j][2]]
                            
    board = deepcopy(new_board)

                                        

print(ans)

• 상어 위치를 리스트로 사용
  
  • 최대 100 x 100으로 전체 탐색에도 문제가 없는듯

https://hoyeonkim795.github.io/posts/17143/

[백준] #17143 낚시왕 python (파이썬)

기억해야할 것

• 까다로운 구현 문제
  
  • 이런 형식의 조건이 까다로운 문제는 시간제한이 있는 경우 어려움
  • 함수로 최대한 분할하여 문제를 접근하기