[백준] 16236 파이썬(python) : 아기 상어 - (★)

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

16236번: 아기 상어

 

 

import sys
from collections import deque
n = int(sys.stdin.readline())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]

shark_size = 2 #1
eat_cnt = 0 #2
fish_cnt = 0 #3
time = 0 #4
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
for i in range(n):
    for j in range(n):
        if graph[i][j] <= 6: #5
            fish_cnt += 1
        elif graph[i][j] == 9: #6
            shark_x, shark_y = i, j
graph[shark_x][shark_y] = 0 #7
 
def bfs(shark_x, shark_y):
    q = deque()
    q.append((shark_x, shark_y, 0))
    dist_list = []
    visit = [ [False]*n for _ in range(n) ]
    visit[shark_x][shark_y] = True
    while q:
        x, y, dist = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visit[nx][ny]:
                if graph[nx][ny] <= shark_size: #8
                    visit[nx][ny] = True
                    if 0 < graph[nx][ny] < shark_size: #9
                        dist_list.append((dist+1, nx, ny))
                    else: #10
                        q.append((nx, ny, dist+1))
    if dist_list:
        dist_list.sort() #11
        return dist_list[0]
    else:
        return False #12
while fish_cnt:
    result = bfs(shark_x, shark_y)
    if not result:
        break
    shark_x, shark_y = result[1], result[2] #13
    time += result[0] #14
    eat_cnt += 1 #15
    fish_cnt -= 1 #16
    if shark_size == eat_cnt: #17
        shark_size += 1
        eat_cnt = 0
    graph[shark_x][shark_y] = 0 #18
print(time)

 

#1 : 아기상어 크기 초기화

#2 : 아기상어의 크기 저장하는 변수

#3 : 물고기 수를 저장할 변수

#4 : 엄마상어를 부르는 시간

#5 : 크기가 6까지는 물고기

#6 : 크기가 9인 경우는 아기상어 위치

#7 : 아기상어가 있던 위치는 0처리. 후에 몸의 크기 비교로 구분하는데 9로 남아있으면 곤란함. 0으로 지정해야 다른 물고기를 찾을때 자신이 있던 자리를 이동할 수 있음.

#8 : 아기상어 크기보다 같거나 작으면 이동할 수 있음

#9 : 1보다 크고 아기상어 크기보다 작으면 먹을 수 있는 물고기, 최소거리를 먹을 수 있는 물고기까지의 사이거리로 갱신해주고 이동한 거리+1과 그 물고기의 위치 리스트에 저장

거리를 첫번째 원소로 삽입하는 이유는 후에 리스트를 정렬할때 두번째나 세번째에 있으면 lambda함수를 이용해서 정렬해 줘야 하기 때문에 편하게 첫번째 원소로 삽입하고 정렬하면 최소거리를 기준으로 리스트가 정렬이 된다

#10 : graph[nx][ny]이 0이거나 자신과 같은 크기의 물고기일때 (#8은 만족하지만 잡아먹을 수 없는 경우)

#11 : 현재의 위치 x, y에서 가능한 모든 물고기들을 삼킨뒤 그 거리와 위치를 dist_list에 저장했으니 문제에서 가장 가까운 거리의 물고기 부터 먹으라는 조건을 수행하기 위해 오름차순 정렬을 해주고 최단거리인 첫번째 요소만 남기고 나머지는 버림으로써 가장 가까운 물고기만 먹는것으로 간주

#12 : 끝날때까지 아무 물고기도 먹지 못하면 False반환

#13 : 최소거리에 있던 물고기를 먹은 위치 아기상어의 위치로 갱신

#14 : 이동한 거리만큼 시간추가(거리 1 이동하는데 1초의 시간이 걸린다고 정했으므로 거리와 시간은 동일시된다)

#15 : 먹은 물고기 수 +1

#16 : 전체 물고기 수 -1

#17 : 먹은 물고기 수와 아기상어 크기가 같으면 크기 +1

#18 : 아기상어의 새로운 위치 0으로 갱신

 

 

어렵다. 위치 이동하는 조건에 대해 좀 더 고민해봐야 할것 같다.