[SWEA] 1249 [S/W 문제해결 응용] 4일차 - 보급로 파이썬

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

 

시작점에서 출발하여 가중치인 복구 시간을 가장 적게 하면서 도착지로 이동하는 문제이다.

우선순위 큐를 사용하여 BFS로 구현했다.

우선순위 큐는 heapq 패키지로 사용하여 복구시간을 최우선기준으로 잡고 했다.

 

import heapq

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

tc = int(input())

visited = [[0]*100 for _ in range(100)]
visited_num = 0

def solv(t):
    global n,board
    n = int(input())
    board = [list(map(int, input())) for _ in range(n)]

    print('#%d %d'%(t,bfs()))
def bfs():
    global visited

    visited[0][0] = visited_num

    pq = []
    heapq.heappush(pq,(0,0,0))

    while pq:
        cnt,x,y = heapq.heappop(pq)

        x *= -1
        y *= -1
        if x == n-1 and y == n-1:
            return cnt

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny):
                visited[nx][ny] = visited_num
                heapq.heappush(pq,(cnt+board[nx][ny],-nx,-ny))
def point_validator(x,y):
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    elif visited[x][y] == visited_num:
        return False
    return True
for t in range(1,tc+1):
    visited_num += 1
    solv(t)