내 인생 이대로 ㅈ될 수 없다

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

내 풀이

from collections import deque
import sys
INF = 10**8
input = sys.stdin.readline

def solution():
    K = int(input())
    graph = [list(map(int,input().split())) for _ in range(K)]

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

    shark = 2
    now_x,now_y=0,0

    for i in range(K):
        for j in range(K):
            if graph[i][j]==9:
                now_x,now_y = i,j
                graph[now_x][now_y] = 0


    def bfs():
        dist = [[-1] * K for _ in range(K)]
        q = deque([(now_x,now_y)])
        dist[now_x][now_y]=0

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

                if 0<=nx <K and 0<=ny <K:
                    if dist[nx][ny] == -1 and graph[nx][ny] <= shark:
                        dist[nx][ny] = dist[a][b] + 1
                        q.append((nx,ny))
        return dist


    def find(dist):
        x,y=0,0
        min_dist=INF
        for i in range(K):
            for j in range(K):
                if dist[i][j] != -1 and 1<= graph[i][j] <shark:
                    if dist[i][j] < min_dist:
                        x,y = i,j
                        min_dist = dist[i][j]
                        
        if min_dist == INF:
            return None
        else:
            return x,y,min_dist
        
    result =0
    ate = 0

    while True:
        value = find(bfs())

        if value == None:
            print(result)
            break
        else:
            now_x,now_y = value[0],value[1]
            result += value[2]

            graph[now_x][now_y]=0
            ate +=1

            if ate >= shark:
                shark +=1
                ate = 0
solution()

다른 사람들의 풀이를 보니까 정렬을 했던데, 사실 그럴 필요가 없다고 생각했다. 왜냐면 애초에 최단 거리 테이블을 제공하면 되기때문이다.

bfs로 최단 거리 테이블을 제공, find함수로 가장 가까운 물고기 1마리를 선택하면 된다.

True 인동안 최단 거리에 있는 물고기를 계속해서 탐색하면 될일이다. 

시간 초과의 위험역시 먹을 물고기가 없는 경우에는 바로 함수가 종료되므로 걱정할 일이 없다.

다른사람의 풀이

from collections import deque
n = int(input())
s_x, s_y = -1, -1
s_level, eat = 2, 0
graph = []

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

for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(n):
        if data[j] == 9:
            s_x, s_y = i, j


graph[s_x][s_y] = 0

def bfs(s_x, s_y, s_level):
    visited = [[False]*n for _ in range(n)]
    q = deque()
    q.append((s_x, s_y, 0))
    visited[s_x][s_y] = True
    fish = []
    while q:
        x, y, count = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                if graph[nx][ny] != 0 and graph[nx][ny] < s_level:
                    fish.append((count+1, nx, ny))
                    q.append((nx, ny, count+1))
                    visited[nx][ny] = True
                elif graph[nx][ny] == 0 or graph[nx][ny] == s_level:
                    visited[nx][ny] = True
                    q.append((nx, ny, count+1))

    fish.sort()
    if fish:
        return [fish[0][1], fish[0][2], fish[0][0]]
    else:
        return []

answer = 0

while True:
    fish_eat = bfs(s_x, s_y, s_level)
    if fish_eat:
        x, y, move = fish_eat
        graph[x][y] = 0
        eat += 1
        answer += move
        if eat == s_level:
            s_level += 1
            eat = 0
        s_x, s_y = x, y
    else:
        break

print(answer)