[SW Expert Academy]1249. [S/W 문제해결 응용] 4일차 - 보급로

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1

SW Expert Academy

N*N차원의 배열이 주어질때, S에서 G로 가는 가장 작은 가중치를 찾는 문제이다.

 

 

 

풀이

• BFS기반의 다익스트라로 풀었다.
  • num_maps에 (x,y)위치로 가기 위한 최단 경로가 저장된다
  • 돌아가는 경우가 더 적은 가중치일 경우 업데이트 한다. 

from collections import deque

def dijkstra(x,y):
    dxs=(-1,1,0,0)
    dys=(0,0,1,-1)
    queue=deque()
    queue.append((x,y))
    num_maps[x][y]=0
    visited.add((x,y))

    while queue:
        x,y=queue.popleft()
        for i in range(4):
            dx=dxs[i]
            dy=dys[i]
            if x+dx>=0 and x+dx<len(num_maps[0]) and y+dy>=0 and y+dy<len(num_maps[0]):
                if num_maps[x][y]+maps[x+dx][y+dy]<num_maps[x+dx][y+dy]:
                    queue.append((x+dx,y+dy))
                    visited.add((x+dx,y+dy))
                    num_maps[x+dx][y+dy]=num_maps[x][y]+maps[x+dx][y+dy]


T=int(input())
for t in range(1,T+1):
    N=int(input())
    maps=[]
    num_maps=[]
    visited=set()

    for i in range(N):
        maps.append(list(map(int,input())))
        num_maps.append([100001 for _ in range(N)])

    dijkstra(0,0)

    print(f"#{t} {num_maps[N-1][N-1]}")

 

 

생각해보니, 다익스트라는 보통 우선순위 큐를 이용해서 구현된다.

이 코드는 아래와 같다.

import heapq

def dijkstra(N, maps):
    dxs = [-1, 1, 0, 0]
    dys = [0, 0, -1, 1]

    num_maps = [[float('inf')] * N for _ in range(N)]
    num_maps[0][0] = 0

    heap = []
    heapq.heappush(heap, (0, 0, 0))  # (현재 비용, x 좌표, y 좌표)

    while heap:
        cost, x, y = heapq.heappop(heap)

        if cost > num_maps[x][y]:
            continue

        for i in range(4):
            nx, ny = x + dxs[i], y + dys[i]

            if 0 <= nx < N and 0 <= ny < N:
                new_cost = cost + maps[nx][ny]
                if new_cost < num_maps[nx][ny]:
                    num_maps[nx][ny] = new_cost
                    heapq.heappush(heap, (new_cost, nx, ny))

    return num_maps[N-1][N-1]


T = int(input())
for t in range(1, T + 1):
    N = int(input())
    maps = [list(map(int, input())) for _ in range(N)]

    result = dijkstra(N, maps)
    print(f"#{t} {result}")