[SW Expert Academy]1249번 보급로(heap, dijkstra)

문제의 저작권은 SW Expert Academy에 있습니다.

 

삼성역량평가 A형 기준으로 그래프를 할 필요가 없다고는 하지만, 2019년도에 기출이 되었기 때문에 다익스트라도 알아두고 시험장에 들어가면 좋다.

 

---

 

2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다.

전투가 진행중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다.

그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지날 갈 수 없다.

전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다.

공병대는 출발지(S) 에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다.

도로가 파여진 깊이에 비례해서 복구 시간은 증가한다.

출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오.

깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다.

                                             그림 1 (a) 파손된 도로                                                             (b) 지도 형태와 이동 방향

지도 정보는 그림1(b)와 같이 2차원 배열 형태로 표시된다.

출발지는 좌상단의 칸(S)이고 도착지는 우하단의 칸(G)가 된다.

이동 경로는 상하좌우 방향으로 진행할 수 있으며, 한 칸씩 움직일 수 있다.

지도 정보에는 각 칸마다 파여진 도로의 깊이가 주어진다. 현재 위치한 칸의 도로를 복구해야만 다른 곳으로 이동할 수 있다.
 

그림 2 지도 정보

이동하는 시간에 비해 복구하는데 필요한 시간은 매우 크다고 가정한다.

따라서, 출발지에서 도착지까지 거리에 대해서는 고려할 필요가 없다.

지도 정보는 그림2에서 보듯이 2차원 배열의 형태이다.

출발지(S)와 도착지(G)는 좌상단과 우하단이 되고 입력 데이터에서는 0으로 표시된다.

출발지와 도착지를 제외한 곳이 0인 것은 복구 작업이 불필요한 곳이다.

다음과 같은 지도에서 복구 작업 시간이 최소인 시간은 2이고 회색으로 칠해진 경로가 된다.
 

[입력]

가장 첫 줄은 전체 테스트케이스의 수이다.

각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.

그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.
 
[출력]

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다.

이때 C는 케이스의 번호이다.

같은 줄에 빈 칸을 하나 두고, 주어진 입력에서 출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오.

 

 

---

총 복구 시간을 구하는 문제다.

출발점은 0이다

상하좌우로 움직 일 수 있다. (델타 탐색)

이동 시 숫자 만큼이 복구시간이라고 간주하고 풀어도 된다.

최단경로니까 다익스트라를 쓴다. 

ex) 서울에서 부산을 경유지를 거쳐서 가는데 최단으로 가는 경로를 구하기

이동시간은 무시하고 복구 시간만 보겠다.

제한사항

100곱하기 100 

bfs로 하면 visited를 쓰면 안된다. 왜냐하면, 반문한 부분에 최소 값을 인지하고 바꿔줘야 한다. 그리고 완전 탐색을 해 줘야한다.

 

그래프에서는 다익스트라와 MST(프린과 크루스컬)을 배웠다.

 

Dijkstra 알고리즘

일단 가중치를 전부 무한대로 준다(초기화)

visited도 만들어 준다.

시작점을 무한대에서 0으로 바꿔준다.

시작점에서 최소값을 뽑아온다.(heap우선순위 큐를 쓰면 for 문 2개보단, nlogn 보다 빠르다.)

인접한 정점들을 v라고 하면, v에 가중치 만큼을 업데이트를 한다.

(기본적으로 탐욕(그리디)이기 때문에 가까운것들을 하나씩 한다.)

위에서 선택한 v 에서 인접한거 하나씩 또 구해서 가중치를 넣어 준다.

업데이트 끝날 떄마다, heap으로 가장 작은거 가져온다.

(즉, 기준점에서 가지를 뻗은 후에 끝점 들 중에 가중치가 가장 작은 것들을 가져와서 다시 가지를 뻗고, 끝점들 중 가중치 가장 작을 것을 가져오고... 이런식으로 도착할 때 까지 반복을 계속한다.)

만약 가중치를 적어논 곳에 저 적은 가중치가 계산이 된다면, 값을 적은 값으로 바꿔준다.

 

이때, 경로는 보이지 않고 가중치만 보인다

 

 

우선순위 큐를 heap 말고 풀려면,

2차원 배열에서 가장 작은 값만 주자. 2바퀴 돌면서 min값 구하고, 방문 안한 것들 중에서 visited를 체크하자.

heap(우선순위 큐)

- 완전이진트리

- 최소힙 : 항상 부모가 자식보다 작다.

- heap을 이용해서 sort를 하면 힙소트이다. 힙소트의 시간 복잡도는 O(nlogn)

cf) 퀵소트나 merge도 nlogn이다.

 

import heapq
heap = [7, 2, 5, 3, 4, 6]
heapq.heapify(heap)
print(heap)
heapq.heappush(heap,1)   # 인큐
print(heap)
while heap:
	print(heapq.heappop(heap), end = " ")) # 디큐


#출력은 [2, 3, 5, 7, 4, 6]

####################
temp = [7, 2, 5, 3, 4, 6]
heap2=[]
for i in range(len(temp)):
	heapq.heappush(heap2, (-temp[i], temp[i
heapq.heappush(heap2, (-1, 1))
print(heap2)
while heap:
	print(heapq.heappop(heap)[1], end = " ")) # 디큐

 

위 코드를 실행해서 확인해보자.

---

arr, dist(전부 무한), visited(전부 0). 이렇게 2차행렬 3개 있다

출발점은 (0,0)

코드를 보자.

import sys
sys.stdin=open('1249보급로.txt')
import heapq

def check(x, y):
    if x < 0 or y < 0 or x > N-1 or y > N-1 :
        return False
    if visit[x][y] :
        return False
    return True

def dijkstra(x, y):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    dist[x][y] = 0   # 출발
    heapq.heappush(heap, (dist[x][y], x, y))  # 가중치 , x, y

    while heap:
        d, x, y = heapq.heappop(heap)
        if x == N-1 and y == N-1:
            return
        visit[x][y] =1

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

            if check(nx, ny) and dist[nx][ny] > dist[x][y] + arr[nx][ny]:
                dist[nx][ny] = dist[x][y] + arr[nx][ny]
                heapq.heappush(heap, (dist[nx][ny], nx, ny))



TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    arr = [list(map(int, input())) for _ in range(N)]
    dist = [[999999999] * N for _ in range(N)]
    visit = [[0] * N for _ in range(N)]
    heap = []

    dijkstra(0, 0)
    print(f'#{tc} {dist[N-1][N-1]}')