[백준 16236번] 아기 상어 - Python으로 구현하기

[백준 16236번] 아기 상어 - Python으로 구현하기

 

문제 접근

• 정해진 규칙에 따라 아기 상어의 다음 위치를 정해주어야 한다.
• 거리가 같은 먹을 수 있는 곳이 여러 개인 경우 가장 높고, 가장 왼쪽에 있는 좌표로 이동한다.

 

생각해볼 점

• 짜다보니 하드코딩을 해버렸다. baby shark의 정보들을 깔끔하게 관리하고, 로직도 다시 생각해봐야 겠다.

 

오답 분석

• 거리가 같은 상어들의 우선순위를 정해주지 않으면 오답!

 

def find_shark(baby):
    global map_data,baby_pos,baby_size,baby_eat_cnt,time

    dq = deque()
    dq.append(baby)
    dist = [[-1] * N for _ in range(N)]
    dist[baby[0]][baby[1]]=0
    min_dist=N*N

    while dq:
        x,y=dq.popleft()

        for k in range(4):
            nx = x+di[k][0]
            ny = y+di[k][1]

            if 0<=nx<N and 0<=ny<N and dist[nx][ny]==-1 and map_data[nx][ny]<=baby_size:
                dist[nx][ny]=dist[x][y]+1
                dq.append([nx,ny])
                if 0<map_data[nx][ny]<baby_size:
                    min_dist=min(min_dist,dist[nx][ny])

    next_pos=[]
    for i in range(N):
        for j in range(N):
            if dist[i][j]==min_dist and 0<map_data[i][j]<baby_size:
                next_pos.append([i,j])

    if next_pos:
        next_pos.sort(key=lambda x:(x[0],x[1]))
        baby_pos=next_pos[0]
        baby_eat_cnt+=1
        time += min_dist
        map_data[baby_pos[0]][baby_pos[1]]=0
        return True
    else:
        return False


from collections import deque

N = int(input())
map_data = [list(map(int,input().split())) for _ in range(N)]

baby_size = 2
baby_pos = [0,0]
baby_eat_cnt = 0
di = [[-1,0],[0,-1],[0,1],[1,0]]

for i in range(N):
    for j in range(N):
        if map_data[i][j]==9:
            baby_pos=[i,j]
            map_data[i][j]=0
            break

time = 0
while True:
    if not find_shark(baby_pos):
        break
    if baby_eat_cnt==baby_size:
        baby_eat_cnt=0
        baby_size+=1
print(time)

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!