[백준] 16236 아기 상어 Python

[백준] 16236 아기 상어 Python

먼저, 이 문제가 왜 BFS인지 알아야한다. 삼성전자 코테 필수 유형 중 하나인 상어 시리즈 중 첫 문제를 풀었다.
조건이 까다롭고 빡구현+BFS 유형이다. 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 이동할 수 있는 가장 가까운 물고기로 이동해야하기 때문에 최단거리를 찾는데 BFS함수가 쓰인다.

먼저, 단계를 보면 종료 조건인 '더 이상 먹을 수 있는 물고기가 공간에 없다면 종료해준다'
그리고, 먹을 수 있는 물고기를 알기 위해서 BFS를 돌린다. 현재 아기 상어의 위치를 넘겨주고 북동남서 방향으로 탐색해가며
1. 자기 사이즈 보다 작거나 같은 물고기를 만났을 경우 queue에 넣어주고, 방문 처리를 해준다
2. 자기 사이즈 보다 작은 물고기일 경우 tmp 리스트에 담아준다
3. bfs 리턴할 때, 정렬을 거리,x축,y축 순서대로 정렬해주되, 나중에 stack 방식으로 pop할 것을 생각하여 역순으로 정렬해준다.
4. while 문을 돌리고 tmp 배열이 0이면 종료, 아닐 경우 배열 중 맨 위의 값을 뽑아서 cnt를 증가시켜주고, 아기 상어의 위치를 update 시켜주고, time을 dist+ 시켜준다.

import sys
sys.stdin=open("input.txt")
from collections import deque

n=int(input())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))

size=2 #상어 초기 사이즈
x=0
y=0
for i in range(n):
    for j in range(n):
        if graph[i][j]==9: #상어 좌표 저장하자
            x=i
            y=j

time=0
#북동남서
dx=[-1,0,1,0]
dy=[0,1,0,-1]

def bfs(si,sj,shark_size): #현재 상어 위치와 가장 가까운 애 찾기
    visited=[[-1 for _ in range(n)]for _ in range(n)]
    q=deque()
    q.append((si,sj))
    visited[si][sj]=0
    tmp=[] #먹을 수 있는 상어 담기

    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            if 0<=nx<n and 0<=ny<n and visited[nx][ny]==-1:
                if graph[nx][ny]<=shark_size: #상어 사이즈보다 작거나 같으면 지나갈 수 있음
                    q.append((nx,ny))
                    visited[nx][ny]=visited[x][y]+1
                    #거리 저장해주기
                    if graph[nx][ny]<shark_size and graph[nx][ny]!=0: #물고기가 있음
                        tmp.append((nx,ny,visited[nx][ny]))
    return sorted(tmp,key=lambda x :(-x[2],-x[0],-x[1])) #pop을 해야하기 때문에 제일 끝으로 보냄

cnt=0
while True:
    shark=bfs(x,y,size)

    if len(shark)==0: #더이상 먹을 물고기가 없다
        break

    nx,ny,dist=shark.pop() #먹을 물고기

    #시간 더해주기
    time+=dist
    graph[x][y]=0 #먹었으니깐 돌려놈
    graph[nx][ny]=0
    x=nx
    y=ny
    cnt+=1
    if cnt==size:
        cnt=0
        size+=1
print(time)