2차원 배열에도 사용가능한 다익스트라 알고리즘

1. 문제

 

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

 

SW Expert Academy

SW Expert Academy

 

 

2차원 배열에서 (0,0)에서 (n-1,n-1)로 가는데, 경로에 쓰이는 숫자들의 합이 최소가 되도록 갈때, 그 최솟값을 구하는 문제

 

 

2. 풀이

 

2차원 배열에서도 다익스트라 알고리즘을 사용할 수 있을까?

 

그대로 사용하면 된다

 

2차원 배열을 하나의 그래프로 바꿀려고 시도한 적이 있었는데 그럴 필요도 없다

 

다익스트라 알고리즘이

 

distance 배열을 무한으로 초기화하고, 출발 위치는 0으로 시작한 다음에

 

현재 위치에서 인접한 곳으로 이동을 해보고, 거리가 최소가 되면 distance를 갱신해나가는 방식이잖아

 

2차원 배열에 그냥 그대로 적용하면 된다

 

T = int(input())
 
for tc in range(1,T+1):
     
    INF = 10000000000
 
    n = int(input())
 
    maps = [list(map(int,input())) for _ in range(n)]
 
    distance = [[INF]*n for _ in range(n)]

 

최초 map을 받고, distance를 map과 동일한 크기의 n*n 배열로 초기화시킨다

 

그러면 n*n의 모든 위치 (x,y)에 대하여 distance 배열의 최솟값을 찾아나간다

 

import heapq
 
def dijkstra(x,y,n):
     
    q = []
 
    heapq.heappush(q,(0,(x,y)))
 
    distance[y][x] = 0

 

다익스트라 알고리즘의 첫 시작은 우선순위 큐에 (0,시작위치)를 넣고, distance 배열의 시작 값을 0으로 하잖아?

 

그냥 시작 위치가 (x,y)일뿐 다를건 없다

 

    while q:
         
        dist,(x,y) = heapq.heappop(q)
 
        if distance[y][x] < dist: ##최단거리 배열이, 큐의 최소거리보다 작다면 이미 처리된 노드
             
            continue

 

다음 큐가 빌때까지 반복을 수행하고..

 

우선순위 큐에서 하나씩 빼서.. distance 배열의 값이, 우선순위 큐에서 나온 거리 dist보다 작으면

 

이미 처리된거니까 continue.. 이것도 완전히 동일

 

        ##인접한 곳을 찾아 비용을 계산
 
        for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
             
            dx = x + ni
            dy = y + nj
 
            if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1:
                 
                cost = dist + maps[dy][dx]
 
                if cost < distance[dy][dx]: ##원래 비용보다 작으면..
                     
                    distance[dy][dx] = cost ##최소비용으로 갱신하고
 
                    heapq.heappush(q,(cost,(dx,dy))) #큐에 넣고

 

 

우선순위 큐에서 하나 빼면, 해당 위치 (x,y)와 인접한 곳을 찾아보는데..

 

인접한 곳은 어떻게 찾아?? 그냥 2차원 배열의 4방향 탐색하듯이 찾으면 된다

 

델타배열로 상,하,좌,우 이동한 dx,dy를 구하고..

 

이게 배열의 범위를 벗어났는지 체크하고..

 

안벗어났으면 이동가능하니까 비용 cost 구한 다음에 이게 distance 배열 값보다 작으면 갱신하고..

 

우선순위 큐에 넣어줘..

 

보면 알겠지만..

 

그냥 distance를 map과 동일한 크기의 2차원 배열로 만들었고

 

위치는 (x,y)로 되는거고.. 인접한 위치 이동은 4방향 탐색하듯이 델타배열로 바꾼 것일 뿐

 

나머지는 그냥 다익스트라 알고리즘과 다를게 없다

 

 

import heapq
 
def dijkstra(x,y,n):
     
    q = []
 
    heapq.heappush(q,(0,(x,y)))
 
    distance[y][x] = 0
 
    while q:
         
        dist,(x,y) = heapq.heappop(q)
 
        if distance[y][x] < dist: ##최단거리 배열이, 큐의 최소거리보다 작다면 이미 처리된 노드
             
            continue
         
        ##인접한 곳을 찾아 비용을 계산
 
        for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
             
            dx = x + ni
            dy = y + nj
 
            if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1:
                 
                cost = dist + maps[dy][dx]
 
                if cost < distance[dy][dx]: ##원래 비용보다 작으면..
                     
                    distance[dy][dx] = cost ##최소비용으로 갱신하고
 
                    heapq.heappush(q,(cost,(dx,dy))) #큐에 넣고
 
 
T = int(input())
 
for tc in range(1,T+1):
     
    INF = 10000000000
 
    n = int(input())
 
    maps = [list(map(int,input())) for _ in range(n)]
 
    distance = [[INF]*n for _ in range(n)]
 
    print('#'+str(tc),dijkstra(0,0,n))