[백준][구현] 아기 상어

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

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

16236번: 아기 상어

 

내가 작성한 코드

from collections import defaultdict, deque

dir = [(0, 1), (1, 0), (-1, 0), (0, -1)]

def in_range(r, c, N):
    return 0<=r<N and 0<=c<N

def read_data():
    N = int(input().rstrip())
    shark = tuple
    board = []
    for r in range(N):
        board.append(list(map(int, input().rstrip().split())))
        for c in range(N):
            if board[r][c] == 9:
                shark = (r, c, 2)
                board[r][c] = 0
    return N, board, shark

def select_fish(shark, board, N):
    row, col, size = shark
    q = deque([(row, col, 0)])
    distance = float('inf')
    pos = (float('inf'), float('inf'))

    visited = defaultdict(bool)
    visited[(row, col)] = True
    while q:
        r, c, cost = q.popleft()

        if board[r][c] != 0 and board[r][c] < size:
            if cost < distance:
                distance = cost
                pos = (r, c)
            elif cost == distance and (r, c) < pos:
                pos = (r, c)
            continue

        for d_r, d_c in dir:
            nw_r, nw_c = r+d_r, c+d_c

            if in_range(nw_r, nw_c, N) and board[nw_r][nw_c] <= size and\
                    not visited[(nw_r, nw_c)] and cost+1 <= distance:
                visited[(nw_r, nw_c)] = True
                q.append((nw_r, nw_c, cost+1))

    return pos, distance

def eat(board, pos, shark, ate):
    # 물고기 죽음
    _r, _c = pos
    board[_r][_c] = 0

    # shark 위치/사이즈 변경
    ate += 1
    r, c, s = shark
    if ate == s:
        shark = (_r, _c, s+1)
        ate = 0
    else:
        shark = (_r, _c, s)
    return shark, ate

def get_answer(N, board, shark):
    ate = time = 0
    pos, distance = select_fish(shark, board, N)
    while distance != float('inf'):
        # debug(board, shark, ate, time, pos)
        shark, ate = eat(board, pos, shark, ate)
        time += distance
        pos, distance = select_fish(shark, board, N)
    # debug(board, shark, ate, time, pos)
    return time

def debug(board, shark, ate, time, pos):
    print(f"================={ate}======================")
    for z in board:
        print(z)
    print()
    print(f"shark : {shark}")
    print(f"pos : {pos}")
    print(f"time : {time}")

N, board, shark = read_data()
print(get_answer(N, board, shark))

• 상어 크기 증가 조건
  
  • 상어 크기와 같은 양의 물고기를 먹을 때마다 크기가 증가
    - 상어크기 : 2 / 먹은 물고기 : 2 ------> 상어크기 : 3 / 먹은 물고기 : 0

 

다른 사람이 작성한 코드

None

• 강한 구현문제로 다른 코드를 참고하지 않음

 

기억해야할 것