아기상어

2주전에 풀다가 실패한 아기상어 문제이다. BFS문제인데, 최근 BFS문제를 나름 많이 풀었다고 생각해서 다시 시도해봤다. 하지만 이번에도 풀지 못했다… 결국 다른 분들 블로그를 찾아보며 문제를 풀었는데, 정답을 보면서도 머리가 잘 안굴러갔던 것 같다.

풀릴듯 풀릴듯 계속 정확히 풀지 못해 더 힘들었다.

문제 분석

아기상어의 위치가 9로 주어지고, 다른 물고기들을 잡아먹는데 걸리는 시간을 구하는 문제다. 물고기들의 크기는 1~6사이로 주어지고, 아기상어의 최초 크기는 2다. 이때, 아기상어는 자신의 크기만큼 물고기를 잡아먹으면 몸집이 1씩 커지게 된다. 아기상어는 자신보다 몸집이 작은 물고기들만 잡아먹을 수 있고, 자신보다 몸집이 큰 물고기가 있는 칸은 지나갈 수 없다.

  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹어야한다.
  • 거리가 가까운 물고가가 많다면 가장 위에 그리고 가장 왼쪽에 있는 물고기를 먹어야한다.

내가 계속 실수한, 중요한 포인트가 위의 조건이었다.

2주전에 처음 풀때는 아래의 조건들만 넣어주면 저 조건을 만족시키는 줄 알았다.

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

하지만, 저 조건을 위해서는 매번 한 칸씩 움직일 때 마다, 리스트를 정렬시켜주어야 했다.

  • point=deque(sorted(point))

BFS로 한 칸씩 퍼져나갈 때 마다, 위의 식을 사용해 정렬해줘야 한다. 파이썬을 사용하면서 지금까지 한번도 sorted를 사용해본 적이 없었는데, 이번 기회에 알아간다.

먼저 sort함수는 list 자료형만 가능하며 해당 리스트를 정렬시키고 아무것도 반환하지 않는다. 반면 sorted함수는 다양한 자료형들에 모두 적용가능하며, 정렬된 값을 반환한다.

a=[1,5,6,8,0,6,8]
b=deque(a)
c=set(a)

print(sorted(a))
print(sorted(b))
print(sorted(c))

위의 코드를 실행시키면

[0, 1, 5, 6, 6, 8, 8]
[0, 1, 5, 6, 6, 8, 8]
[0, 1, 5, 6, 8]

아래와 같은 결과를 얻을 수 있다. 반면, sorted를 사용하지 않고, sort()함수를 사용한 후 출력하면, 리스트는 정상적으로 출력되지만, 나머지 자료형에 대해서는 오류가 발생한다.

더욱 자세한 사항들은 코드에 주석으로 남겨놓았다.

CODE

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

n=int(read())
map=list(list(map(int,read().split())) for _ in range(n))

for i in range(n):
    for j in range(n):
        if map[i][j]==9:
        #아기상어가 있는 위치를 입력하고, 해당 위치를 0으로 초기화
            A,B=i,j
            map[i][j]=0

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

def bfs():
    shark_shape=2#최초의 상어 크기는 2다.
    shark_exp=0  #상어가 몸집이 커지기위한 경험치라고 생각하면 된다.
    point=deque([[A,B]])

    answer=0
    flag=False
    #상어가 물고기를 먹었을 때, 첫 번째 for문을 한번만 돌고 탈출할 수 있도록 한다.
    visited=list(list(-1 for _ in range(n)) for _ in range(n))
    visited[A][B]=0
    #BFS를 진행하며 상어가 방문했는지, 방문했다면 해당 점까지의 거리가 몇인지 저장

    while point:
    #자신보다 큰 물고기들에 갇혔다면, 원소들이 지속적으로 point에
    #추가되지 않아, while문이 종료된다.

        term=len(point)
        point=deque(sorted(point))
        #위, 왼쪽에 위치한 먹이들을 우선적으로 먹기 위해 정렬

        for _ in range(term):
            a,b=point.popleft()

            if 0<map[a][b]<shark_shape:
                map[a][b]=0
                shark_exp+=1
                if shark_exp==shark_shape:
                # 경험치가 상어의 몸집만큼 쌓였다면, 레벨업 시키고
                # 경험치를 다시 0으로 초기화
                    shark_exp=0
                    shark_shape+=1
                point=deque()
                answer+=visited[a][b] #해당 점까지의 거리를 더해준다.
                #물고기를 먹은 자리에서 다시 거리를 계산해 나가야 함으로 visited리스트 초기화
                visited=list(list(-1 for _ in range(n)) for _ in range(n))
                visited[a][b]=0
                flag=True

            for x,y in zip(dx,dy):
                ax,by=a+x,b+y
                if 0<=ax<n and 0 <=by<n and visited[ax][by]==-1 and map[ax][by]<=shark_shape:
                    visited[ax][by]=visited[a][b]+1
                    point.append([ax,by])
            if flag:
                flag=False
                break
    return answer
answer=bfs()
print(answer)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]