[Python] 16236 Baekjoon

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

 

코테 공부하면서 계속 정답보면서 시도했는데

난이도가 없지는 않은 문제인데 그래도 시간들여 처음부터 끝까지 구현을 완료하고 통과했으니

올려보는 코드다.

순수 나의 창작 코드랄까..

 

from collections import deque
import heapq
INF = int(1e9)
n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
start = (0,0)
l = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            start = (i, j)
        elif graph[i][j] != 0:
                l.append((graph[i][j],i,j))

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

def bfs(start):
    x,y = start
    array = [[INF] * (n) for _ in range(n)]
    array[x][y] = 0
    q = deque()
    q.append((0,x,y))
    data = []
    graph[x][y] = 0
    while q:
        a,x,y = q.popleft()
        for i in range(4):
            x_0 = x + dx[i]
            y_0 = y + dy[i]
            if 0 <= x_0 < n and 0 <= y_0 < n and graph[x_0][y_0] <= size:
                cost = a + 1
                if cost < array[x_0][y_0]:
                    array[x_0][y_0] = cost
                    q.append((cost, x_0, y_0))
                    if 0 < graph[x_0][y_0] < size:
                        data.append((cost, x_0, y_0))
    if len(data) == 0:
        return False
    else: 
        data.sort()
        return data[0]

size = 2
i = 0  
total = 0
while 1:
    p = bfs(start)
    if p == False:
        break
    v, a, b = p
    total += v
    i += 1
    if i == size:
        i = 0
        size += 1
    start = a, b
print(total)