파이썬)아기상어 -BOJ

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

 

from collections import deque

n = int(input())

arr = []

shark_size = 2
eat = 0
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

shark_x = 0
shar_y = 0
for i in range(n):
    a = (list(map(int, input().split())))
    for j in range(len(a)):
        if a[j] == 9:
            a[j] = 0
            shark_x = i
            shark_y = j
    arr.append(a)


def finding(x, y):
    q = deque()

    q.append((x, y))

    visit = [[False for _ in range(n)] for _ in range(n)]
    distance = [[0 for _ in range(n)] for _ in range(n)]

    can_eat_list = []

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 <= nx < n and 0 <= ny < n:
                if arr[nx][ny] <= shark_size and not visit[nx][ny]:
                    visit[nx][ny] = True
                    distance[nx][ny] = distance[x][y] + 1
                    q.append((nx, ny))

                    if arr[nx][ny] < shark_size and arr[nx][ny] != 0:
                        can_eat_list.append((nx, ny, distance[nx][ny]))

    can_eat_list.sort(key=lambda x: (x[2], x[0], x[1]))

    return can_eat_list


ans = 0

while True:
    fishlist = finding(shark_x, shark_y)

    if len(fishlist) == 0:
        print(ans)
        break

    shark_x, shark_y, move_time = fishlist[0]

    eat += 1
    if shark_size == eat:
        eat = 0
        shark_size += 1

    arr[shark_x][shark_y] = 0

    ans += move_time

문제는 간단한 bfs문제 같았지만 

특수 조건 때문에 좀 까다로웠다.

"거리가 가까운 물고기가 많다면, 가장 위에있는 물고기, 그리고 가장 왼쪽에 있는 물고기를 가장 먼저 먹는다"

과연 이 조건을 어떻게 구현할지 무척 애를 먹었다.

그러다 결국 다른 사람의 정답을 보게되었다.

해결법은 간단했다.

우선 현재 경로가 최적의 경로라는 bfs의 특징을 이용해 물고기를 발견하면(먹을 수 있는 물고기) 어떤 리스트에 x,y좌표와 함께 거리를 담는다.

그리고 위 조건을 "정렬"을 이용해 만족시키며 되는 것이다.

우선 거리가 가까운 순으로 정렬시키고, x좌표 중 위에있는 순으로 정렬, 그다음 y좌표 중 왼쪽에 있는 순으로 정렬해 그 리스트의 0번째를 리턴시킨다.

생각해보면 이런 생각을 왜 못했나싶을 정도로 간단한 문제였다.