[백준 16236번 | 골드3] 아기상어 파이썬 풀이

반년 정도 전에 백준 열심히 풀 때 못 풀었던 문제를 오히려 오랜만에 푸니깐 바로 풀어서 공유해봅니다.. (코드가 더러워도 이해 부탁)

 

문제: 아기상어가 물고기 먹으러 댕길건데 0이나 자기랑 같은 크기의 물고기는 지나갈 수 있고, 자기보다 작은 물고기만 먹을 수 있음. 물고기를 먹으러 갈 때는 가장 가까운 놈을 먹어야 하는데 같은 거리에 물고기가 많다면 제일 윗쪽, 그리고 왼쪽에 있는 물고기를 먹어야함. 자신의 크기만큼 물고기를 먹으면 성장함.

 

여기서 'BFS로 풀고, 탐색할 때 윗쪽, 왼쪽, 오른쪽, 아래 이 순서로 탐험하면 되겠다.'라고 생각하는 것이 일반적이라 생각한다. 나 또한 그랬고, 질문 게시판에도 많은 사람들이 같은 생각을 하고 있다. 하지만 일반적인 BFS로는 앞에서 말한 순서로 실행해도 가장 위에 있고, 가장 왼쪽에 있다는 것을 보장해주지 않는다.

 

예제4 예시

 

코드는 아래와 같다.

import sys
from collections import deque

#함수부
def explore(x1, y1, t):
    global l, count, tm, visited, que, m, mx, my, mt
    if m[x1][y1]>0 and m[x1][y1]<l:#먹이이면서 자기보다 작아서 먹을 수 있으면 냠냠
        #첫 먹이의 좌표를 저장
        mx = x1
        my = y1
        mt = t
        #이 문제의 하이라이트. bfs가 탐험순서를 위, 왼쪽, 오른쪽, 아래 순으로 시켜도 최초 발견된 것이
        #가장 위고 왼쪽이란걸 보장하지 않으므로 현재 que에 들어있는 것들까지는 탐험해봐야함
        while que:#que에 남아있는 것들만 먹이를 발견하는지 체크
            x2, y2, tix = que.popleft()
            if x2>0:
                explore2(x2-1,y2,tix)
            if y2>0:
                explore2(x2,y2-1,tix)
            if y2<N-1:
                explore2(x2,y2+1,tix)
            if x2<N-1:
                explore2(x2+1,y2,tix)
        count+=1
        tm+=mt+1
        m[mx][my]=0
        if count==l:
            l+=1
            count=0
        #visited 초기화 및 deque 초기화 + 현재 위치 넣기
        que = deque()
        que.append((mx,my,0))
        visited = [[0]*N for _ in range(N)]
        visited[mx][my]=1
        return False
       
    elif visited[x1][y1]==0 and m[x1][y1]<=l:#이동할 수 있는 곳이면 que에 추가 및 방문 체크
        visited[x1][y1]=1
        que.append((x1,y1,t+1))
    return True
    
def explore2(a, b, tt):#첫 먹이 발견 후 que에 남아있는 좌표에 있는 먹이가 먹을 수 있는 먹이인지만 판단
    global mx, my, mt, l
    if m[a][b]>0 and m[a][b]<l:
        if tt<=mt:
            if a<mx or (a==mx and b<my):
                mx=a
                my=b
                mt=tt
                
input = sys.stdin.readline
N = int(input())
m = []#map
location = (N+1,N+1)
for i in range(N):
    m.append(list(map(int,input().split())))
    #첫 출발 찾을 때까지만 돌리도록
    if location[0]==N+1:
        for j in range(N):
            if m[i][j]==9:
                location = (i, j)
                m[i][j]=0
que = deque()
que.append((location[0],location[1],0))
l=2 #fish-length
count = 0 #feed count
tm = 0 #total time

#explore2에서 더 위에 있고 왼쪽에 있는 먹이를 찾았을 때 x, y, t를 갱신하기 위한 변수 선언
mx= 0
my = 0
mt =0

#방문기록
visited = [[0]*N for _ in range(N)]
visited[location[0]][location[1]]=1

#기본적인 bfs 위, 왼쪽, 오른쪽, 아래 탐색하는 코드
while que:
    x, y, tic = que.popleft()
    if x>0:
        if explore(x-1,y,tic)!=True:
            continue
    if y>0:
        if explore(x,y-1,tic) != True:
            continue
    if y<N-1:
        if explore(x,y+1,tic)!=True:
            continue
    if x<N-1:
        if explore(x+1,y,tic) != True:
            continue

print(tm)

 

BFS 실력을 한층 더 높혀주는 좋은 문제고, 조금만 더 생각하면 답을 찾을 수 있는 골드3에 어울리는 문제인 것 같다.