[baekjoon] 백준 16236번 : 아기 상어 (by python 파이썬) bfs, lambda정렬

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

16236번: 아기 상어

 

정답 code

#아기 상어
from collections import deque
import sys 
input = sys.stdin.readline

dx = [-1,1,0,0]
dy = [0,0,1,-1]

def bfs(x,y,shark_size):
    distance = [[0]*n for _ in range(n)]  #거리 저장
    visit = [[0]*n for _ in range(n)]  #방문 여부 저장
    queue = deque()
    queue.append((x,y))
    visit[x][y] = 1  #방문처리
    eat = [] #먹을수 있는 물고기의 좌표, 거리 저장하기 위함

    while queue:
        ix,iy =  queue.popleft()
        for i in range(4):
            nx = dx[i] + ix
            ny = dy[i] + iy
            #새로운 좌표가 n*n공간 안에 있고 방문한적 없을때
            if 0<=nx<n and 0<=ny<n and visit[nx][ny] == 0:
                #물고기크기가 상어보다 작거나 같은경우
                if space[nx][ny] <= shark_size:
                    queue.append((nx,ny))
                    visit[nx][ny] = 1
                    distance[nx][ny] = distance[ix][iy] + 1
                    #물고기가 있고, 물고기크기가 상어보다 작은 경우
                    if space[nx][ny] < shark_size and space[nx][ny] != 0:
                        #해당 물고기의 위치(nx,ny), 물고기까지의 최소 거리(distance) 저장
                        eat.append((nx,ny,distance[nx][ny]))

    #특정 순서 기준으로 정렬 하기 위해 lambda함수 사용
    #x[2]: 거리 / x[0]: 행 / x[1]: 열 순으로 내림차순정렬 - pop으로 꺼내기위함
    return sorted(eat, key = lambda x : (-x[2],-x[0],-x[1]))
                    


n = int(input()) #공간 크기
space = [list(map(int,input().split())) for _ in range(n)]
cnt = 0
result = 0
x,y,size = 0,0,2

for i in range(n):
    for j in range(n):
        if space[i][j] == 9 :
            x = i
            y = j


#while 1회 순환시 물고기 한마리 잡아 먹음   
while 1:
    #좌표에서 부터 가장 가까운 물고기 좌표, 거리 찾기
    shark = bfs(x,y,size)

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

    #상어보다 작은 물고기 좌표 nx,ny, 물고기까지의 최소거리 dist 로 저장
    nx,ny,dist = shark.pop()

    #거리 1 = 1초 // 결과에 거리 저장
    result += dist
    #상어있던 위치 or 잡아먹은 물고기위치 숫자 0 으로 바꿔줌
    space[x][y], space[nx][ny] = 0,0

    #잡아먹은 물고기 좌표 nx, ny 부터 다시 bfs 탐색하기 위해
    x, y = nx,ny

    #물고기 먹을때 마다 cnt 추가
    cnt += 1

    #상어크기와 같은 수의 물고기를 먹으면 size(크기)+ 1
    if cnt == size:
        size += 1
        cnt = 0

print(result)

 

solution

애로사항은 처음에 while문에 담긴 조건사항을 모두 bfs내에서 해결하려하다보니 어느정도 틀은 잡혔는데 세부 조건들에 대해 진척이 없었다.

while문을 통해 먹을수있는 물고기가 없을때까지 가까운 거리순으로 bfs함수를 돌려줌으로써 해결할 수 밖에 없었다.

 

큰틀만 설명하자면 bfs함수를 통해 현재 먹을 수있는 물고기(= 자신보다 작은 크기)의 물고기의 좌표와 최단거리를

eat함수에 저장한다음 값이 여러개이면 거리/행/열 순으로 리턴해준다. 

 

이때 lambda함수를 통해 우선순위 정렬을 해주는데 -를 붙이는 이유는 나중에 작은것부터 pop을 이용해 사용하는데

거리/행/열 순으로 가장 작은걸 오른쪽에 배치해 가장 먼저 꺼내지도록 하기 위함이다.

 

만약 먹은 물고기의 갯수가 크기와 같다면 상어 크기(size)를 +1 해주고 

마지막으로 먹은 물고기 좌표부터 시작해주면 된다.

 

상세 내용은

코드가 길어 설명을  주석 처리하였다.