[Python] 백준16236 아기 상어

04 Feb 2023 in Study on Algorithm

백준16236 아기 상어 링크

문제

예제 입력

---

코드

import sys
from collections import deque 

n = int(input())
arr = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0] 
def BFS(y, x, size):
    fishes = []
    dq = deque()
    dq.append([0, y, x]) # 거리, 위치
    visit = [ [0] * n for _ in range(n) ]
    visit[y][x] = True

    while dq :
        dist, oy, ox = dq.popleft()
        for i in range(4):
            ny = oy + dy[i]
            nx = ox + dx[i]
            if 0 <= nx < n and 0 <= ny < n and not visit[ny][nx]:
                if 0 <= arr[ny][nx] <= size: # 빈칸과 상어와 크기가 같을때
                    dq.append([dist+1, ny, nx])
                    visit[ny][nx] = True
                    if 0 < arr[ny][nx] < size: # 먹은 물고기
                        fishes.append([dist+1, ny, nx])

    fishes.sort()
    if fishes: # 가장 가까운 물고기
        return fishes[0]

# 처음 상어 위치
for i in range(n):
    for j in range(n):
        if arr[i][j] == 9:
            shark_y, shark_x = i, j
            arr[i][j] = 0

# 시뮬레이션
ans = 0
shark_size, shark_eat = 2, 0
while True:
    # 현재 위치에서 먹을 수 있는 물고기가 있는지 확인
    res = BFS(shark_y, shark_x, shark_size)

    # 없으면 종료
    if res is None:
        print(ans)
        break

    # 먹은 물고기에 대한 정보
    fish_dist, fish_y, fish_x = res
    arr[fish_y][fish_x] = 0
    shark_y, shark_x = fish_y, fish_x
    shark_eat += 1
    ans += fish_dist

    # 크기 증가
    if shark_size == shark_eat:
        shark_size += 1
        shark_eat = 0

설명

파이썬을 통해서 사용자로부터 입력받아 BFS알고리즘과 시뮬레이션알고리즘을 사용하여 아기 상어를 구현했습니다.

---

결과