[python3] 백준 16236 풀이 ( 아기상어, 그래프, BFS, sort, pq? )

이번 문제도 역시나 좀 헤맸다. 이번 문제는 BFS로 쉽게 풀릴 줄 알고 살짝 깝쳐 봤으나 역시나 생각치 못한 케이스가 존재해서 결국 다시 코딩한 문제이다. 

문제를 쓰악 읽어보자.

우선 문제는 아기상어의 성장에 관한 이야기다. 스토리처럼 느껴져서 문제 읽는 동안 재밌었다.
여튼 문제에서 나오는건 아기 상어가 성장하기 위해서 물고기를 먹어야한다. 그런데 먹이를 먹는데 여러 조건이 존재한다.

조건
1. 먹을 수 있어야함. (자기보다 크기가 작아야함.)
2. 거리가 가까워야 함.
3. 위 물고기 선호
4. 왼쪽 물고기 선호

1번 조건과 2번 조건은 BFS로 최단 경로를 찾으며 먹을 수 있는 물고기를 찾으면 된다.
3번 조건과 4번 조건은 같은 거리에 존재하는 물고기들의 좌표를 비교하여 조건에 맞는 물고기부터 먹는다.
만약 물고기를 먹는다면 상어의 위치가 달라지고 다시 조건에 맞는 물고기를 찾아 먹으면 된다.

처음에는 BFS로 돌때 "상 좌 우 하"로 돌면서 물고기를 먹고 다시 BFS시켜주면 되겠다고 생각했다. 그러나 그럼 안풀린다. 왜냐하면 BFS만 돌게 되면 조건에 맞지 않게 물고기를 먹는 경우가 발생한다.

0 0 0 0 0
0 0 0 0 0
0 0 9 0 1
0 1 0 0 0
0 0 0 0 0

위와 같이 그래프가 주어진 경우 "상 좌 우 하"로 도는 경우 [3,1]의 값을 먼저 만나게 된다.
조건에 의하면 거리가 같은 경우 위쪽의 물고기를 먹어야 하므로 [2,4]를 먼저 먹어야 한다. 따라서 BFS만으로는 문제를 해결할 수 없다.

따라서 먹을 수 있는 물고기 배열을 만들어서 BFS로 탐색을 진행하며 1개인 경우는 바로 먹고,
물고기가 여러 개인 경우 배열을 정렬하여 가장 조건에 부합하는 물고기를 먹으면 된다.
이후에는 아기 상어의 위치를 물고기 위치로 바꾸고 다시 BFS를 실행한다.

세부적인 정보인, 물고기가 레벨업하고 몇개 먹어야 되고, 얼마나 오래 살았는지는 BFS함수 실행할 때 넘겨주면 끝난다.
이제는 코드를 통해 이해하면 될 것 같다.

'''
조건
1. 먹을수 있어야함. -> 먹을수 있는것만 mq에 저장
2. 거리가 가까워야함. -> 주위 돌때마다 확인
3. 위 물고기 선호
4. 왼쪽 물고기 선호
=> BFS 탐색 -> 물고기 전부 찾기 -> 하나면 하나먹으러 가기
-> 여러개면 조건에 따른 우선순위중 첫번째만 먹기
-> 다시 BFS탐색시작

q 에는 상어의 위치, 레벨, 먹을 물고기수, life
mq 에는 물고기의 y좌표,x좌표
visited 필요함. 단 먹이 먹으면 갱신
map은 전역으로 변경해줌
'''
n = int(input())
Map =[]
shark = 0
for y in range(n):
    tmp = list(map(int, input().split()))
    for x in range(n):
        if tmp[x] == 9:
            shark = [y,x]
    Map.append(tmp)

from collections import deque
from time import sleep
def BFS(sharkinfo):
    dy = [-1,1,0,0] # 상하좌우
    dx = [0,0,-1,1]

    loc, size, ex, life = sharkinfo

    visited = [[0 for i in range(n)] for i in range(n)]
    visited[loc[0]][loc[1]] = 1
    Map[loc[0]][loc[1]] = 0 # 자신이 출발하는 곳은 비어있게 한다.
    
    q = deque([loc])
    mq = deque([])

    time  = 0
    while q:
        time += 1
        for _ in range(len(q)):
            loc = q.popleft()
            y,x = loc
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if (0<=ny<n) and (0<=nx<n) and visited[ny][nx]==0 and Map[ny][nx] <= size: # 움직일수 있는 조건
                    # 먹을수 있는지
                    if 0< Map[ny][nx] < size: # 먹을수 있는 경우 pq에 저장
                        mq.append([ny,nx])
                    else: # 지나갈 수만 있다면 q에 저장
                        q.append([ny,nx])
                    visited[ny][nx] = 1
        # 한바퀴 돌았기 때문에 여기서 pq에 들어간게 있으면 뽑아서 BFS실행시킨다.
        if len(mq) != 0: # 먹을놈들 발견
            mq = deque(sorted(mq, key=lambda x : (x[0],x[1])))
            my,mx = mq.popleft() # 가장 조건에 부합하는 물고기쉑 뽑기
            # 먹이주기
            if ex == 1: # 렙업시기
                size += 1
                ex = size
            else: # 렙업시기 아님
                ex -= 1
            return BFS([[my,mx], size, ex, life + time])
    
    return life

print(BFS([shark,2,2,0]))

 

결론 : 골드문제를 우습게 보지 말자. sorted(list, key=lambda x: (x[0],x[1]) ) 이거 좀 까먹지 말자....