[삼성SW역량][Python/BOJ] 백준 16236 아기상어(BFS,구현)

 

주의해야할 점은 list를 pop()하면 뒤의 원소(마지막원소)부터 반환된다는 것이다. 

그래서 먹을 수 있는 물고기의 리스트를  역순으로 정렬해야한다. 

 

 

이렇게 ! 

return sorted(tmp, key = lambda x : (-x[2],-x[0],-x[1])) 

또는 reverse = True를 뒤에 달아줘도 된다. 

return sorted(tmp, key = lambda x : (x[2],x[0],x[1]), reverse = True)

또는 pop(0)로 바꾸면 된다. 

 

아래 코드는 pop(0)로 만들었다. 

 

 

 

 

 

BFS는 항상 최단거리만을 나타낸다는 점을 이용한다. 

 

1. 아기상어의 위치를 구한다. 

2. biteFish라는 함수를 수행한다.(인수로는 상어의 위치와 상어의 길이를 준다.)

    2-1. 인수로 들어온 상어의 위치에서 BFS를 돌린다.

    2-2. 돌면서 먹을 수 있는 물고기의 좌표와 상어와의 dist를 tmp라는 리스트에 저장한다.

    2-3. tmp에 저장된 먹을 수 있는 물고기들을 정렬하여 반환한다.

     <가장 가까운 물고기, 가장 위에 있는 물고기, 왼쪽에 있는 물고기 > 

     => dist가 작고, x값이 작고, 왼쪽에 있는 물고기 순으로 reverse로 정렬한다. (위에 적어둔 코드 참고)

 

 

 

 

코드 : 

from collections import deque
from itertools import combinations as c 


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


def eatingList(x,y,size) :
    vis = [[0]*n for i in  range(n)]
    dist = [[0]*n for i in  range(n)]
    
    d = deque([[x,y]]) # 상어의 현재위치
    tmp = []
    while d :
        x,y = d.popleft()
        for i in  range(4) :
            nx,ny = dx[i]+x, y + dy[i]
            if 0<=nx<n and 0<=ny<n and vis[nx][ny] ==0 :
                if mp[nx][ny] <= size : # 작거나 같을 경우 
                    vis[nx][ny] = 1
                    dist[nx][ny] = dist[x][y]+1 
                    d.append([nx,ny])
                    if mp[nx][ny] < size and mp[nx][ny] != 0 : #특히 작을 경우 먹을 생선임
                        tmp.append([nx,ny,dist[nx][ny]])
        tmp.sort(key = lambda x : (x[2],x[0],x[1]) )
    return tmp
                


            
            
if __name__=="__main__" :
    n = int(input())
    mp = [list(map(int,input().split())) for i in range(n)]
    
    #  상어자리 확인 
    for i in range(n) :
        for j in range(n) :
            if mp[i][j] == 9 :
                x,y = i,j
                mp[i][j] = 0
                break
    time,cnt,size = 0,0,2
    while True :
        
        fish = eatingList(x,y,size)
        
        # 먹을 물고기가 없다면 
        if len(fish)==0 :
            print(time)
            exit(0)
        
        # 조건에 만족하는 순서대로 정렬한 먹을 수 있는 물고기의 리스트 
        eat = fish.pop(0)
        
        # 먹을 수 있는 물고기 자리로 위치 변경 
        x,y = eat[0],eat[1]
        
        # 먹어서 없앰 
        mp[x][y] = 0
        
        # 그곳으로  간 시간을 소요시간에 더함 
        time += eat[2]
        
        # 먹은 횟수 
        cnt+=1 
        if cnt == size:
            cnt = 0
            size +=1

 

 

 

 

 

 

 

 

참고 블로그 : 

 

https://resilient-923.tistory.com/357

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