[BOJ] 아기상어

16236 아기 상어 boj

import sys
from collections import deque
input = sys.stdin.readline

size = int(input())
board = []
for _ in range(size):
    board.append(list(map(int, input().split())))
# print(board)

for j in range(size):
    for i in range(size):
        if board[j][i] == 9:
            cur = (j, i)
            board[j][i] = 0
            break

csize = 2 # 아기 상어 현재 사이즈
cnum = 0 # 현재 먹은 물고기 수
time = 0

def distance(cur): # cur 위치에서 다음으로 갈 점의 위치
    v = deque([(cur)])
    visited = set()
    visited.add(cur)
    d = 0
    while v:
        nxt = []
        while v:
            y,x = v.popleft()
            if 0 < board[y][x] < csize:
                return (y,x, d)
            for (j,i) in [(y-1,x),(y,x-1),(y,x+1),(y+1,x)]:
                if 0 <= j < size and 0 <= i < size and board[j][i] <= csize and (j,i) not in visited:
                    nxt.append((j,i))
                    visited.add((j,i))
        nxt.sort(key = lambda x: (x[0],x[1]))
        v = deque(nxt)
        d+=1
    return -1

while True:
    # 가장 가까운 점을 가져오기
    nxt = distance(cur)
    if nxt == -1:
        break
    y,x,d = nxt
    board[y][x] = 0
    time += d
    cnum += 1
    if csize == cnum:
        csize += 1
        cnum = 0
    cur = (y,x)
print(time)

---

• def distance(cur) : cur(현재위치)에서 다음으로 갈 점의 위치와 거리를 return 한다

def distance(cur): # cur 위치에서 target 까지 가는 최소 거리
    v = deque([(cur)])
    visited = set()
    visited.add(cur)
    d = 0
    while v:
        nxt = []
        while v:
            y,x = v.popleft()
            if 0 < board[y][x] < csize:
                return (y,x, d)
            for (j,i) in [(y-1,x),(y,x-1),(y,x+1),(y+1,x)]:
                if 0 <= j < size and 0 <= i < size and board[j][i] <= csize and (j,i) not in visited:
                    nxt.append((j,i))
                    visited.add((j,i))
        nxt.sort(key = lambda x: (x[0],x[1]))
        v = deque(nxt)
        d+=1
    return -1

현재 위치에서 다음에 어느 점으로 가야할 지, 그리고 그 점까지 얼마나 걸리는 지를 확인하기 위한 함수이다. v는 현재 d번 이동한 후 갈 수 있는 점들의 모임이다. nxt 에는 현재 v의 점에서 그 후에 갈 수 있는 점들을 넣는다. 만약 그 점이 csize(현재 아기 상어의 사이즈)보다 작다면 그 점은 먹을 수 있는 물고기가 있으므로 바로 거리와 함께 위치를 return 해준다. 아니라면 csize와 같은 물고기는 지나갈 수는 있지만 먹을수는 없다. nxt와 visited에 넣어준다.
nxt.sort(key = lambda x: (x[0],x[1]))
이부분은 거리가 같은 물고기들을 가장 위, 가장 왼쪽 순으로 정렬하는 부분이다.

---

while True:
    # 가장 가까운 점을 가져오기
    nxt = distance(cur)
    if nxt == -1:
        break
    y,x,d = nxt
    board[y][x] = 0
    time += d
    cnum += 1
    if csize == cnum:
        csize += 1
        cnum = 0
    cur = (y,x)
print(time)

위 함수를 이용하여 실제 전체 거리를 찾는 코드이다.
distance 함수를 이용하여 다음 점과 거리를 구한다. 만약 -1이 return 되었다면 이는 이제 먹을 수 있는 점이 없음을 의미하므로 while 문을 중지한다. 그렇지 않은 경우에는 nxt 에서 다음 y,x 좌표를 구해 그 부분은 빈 공간 처리를 해주고, 해당 점까지 가는 시간을 time 에 더해준다. cnum 은 현재 아기 상어가 먹은 물고기의 수이다. cnum이 증가하여 csize가 되면 csize를 하나 늘려주고, cnum은 리셋해준다. (아기상어는 자신과 크기가 같은 수의 물고기를 먹을 때마다 크기가 1 증가)