보급로 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 1249

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

deque 풀이

heapq 풀이

PriorityQueue 풀이

 

---

1. 문제 설명

2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다. 전투가 진행중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다. 그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지날 갈 수 없다. 전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다. 공병대는 출발지(S) 에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다. 도로가 파여진 깊이에 비례해서 복구 시간은 증가한다. 출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오. 깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다. 지도 정보는 그림1(b)와 같이 2차원 배열 형태로 표시된다. 출발지는 좌상단의 칸(S)이고 도착지는 우하단의 칸(G)가 된다. 이동 경로는 상하좌우 방향으로 진행할 수 있으며, 한 칸씩 움직일 수 있다. 지도 정보에는 각 칸마다 파여진 도로의 깊이가 주어진다. 현재 위치한 칸의 도로를 복구해야만 다른 곳으로 이동할 수 있다. 이동하는 시간에 비해 복구하는데 필요한 시간은 매우 크다고 가정한다. 따라서, 출발지에서 도착지까지 거리에 대해서는 고려할 필요가 없다. 지도 정보는 그림2에서 보듯이 2차원 배열의 형태이다. 출발지(S)와 도착지(G)는 좌상단과 우하단이 되고 입력 데이터에서는 0으로 표시된다. 출발지와 도착지를 제외한 곳이 0인 것은 복구 작업이 불필요한 곳이다. 다음과 같은 지도에서 복구 작업 시간이 최소인 시간은 2이고 회색으로 칠해진 경로가 된다.

 

입력

가장 첫 줄은 전체 테스트케이스의 수이다. 각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다. 그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.

출력

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다. 같은 줄에 빈 칸을 하나 두고, 주어진 입력에서 출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오.

예시

입력	출력
10 4 0100 1110 1011 1010 6 011001 010100 010011 101001 010101 111010 8 . . .	#1 2 #2 2 . . .

---

2. 문제풀이

문제가 길지만 읽어보면 하나로 정의된다. 목적지 까지 최소비용이 얼마인가? 2일전 포스팅에도 비슷한 문제가 있었다. 다익스트라 알고리즘을 이용하여 해당위치마다 최소비용을 갱신해 최종 목적지까지의 최소비용을 계산하는 방식이다. 여기의 경우 상하좌우 방향으로 이동이 가능하다. 따라서 이동할때 편하게 계산하기 쉽도록 move를 정의해준 다음 반복문을 이용하여 이동시켰다. 그리고 BFS와 합쳐 새로 갱신될때마다 그것을 기준으로 다시 계산하도록 만들었다. deque를 이용한 이유는 deque는 앞의 원소를 꺼낼때 O(1)이기 때문이다. list는 뒤에서 꺼낼때는 O(1)인데 제일 앞에있는 원소를 꺼내려면 O(n)만큼 시간이 걸린다. --------------------------------------------------------------------------------------- 오리지널 버전으로도 풀어보았다. 다익스트라의 경우 가장 값이 적은 노드를 선택하여 비용을 갱신시키는 방식으로 동작한다. 위의 경우 bfs(deque이용)와 섞었기때문에 연산횟수가 많다. 이를 줄여보기 위해 오리지널로 풀어보았다. 방법은 간단했다. 우선순위큐priority queue와 heapq를이용하여 돌려보았다. 연산횟수와 시간은 아래 사진으로 첨부했다.  -------------------------------------------------------------------------------------- 결과는 아래와 같다. 연산횟수는 heapq와 priority queue를 쓰는것이 확실히 적었다. 그렇지만 내부적으로 작은값을 출력하기위해 정렬하는 과정에서 시간이 많이걸려서 그런지 연산횟수가 많지만 정렬을 하지않는 deque를 이용한 풀이가 더 빨랐다.

heapq, priority queue

deque

위에서부터 heapq, priority queue, deque

---

3. 소스코드

# D4 1249 보급로
from collections import deque
 
# 상하좌우 이동계산용
move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
 
# 다익스트라 알고리즘 계산 함수
def dijkstra(queue):
    # 큐가 빌때까지 반복
    while len(queue):
        # 좌표를 꺼내서
        y, x = queue.popleft()
        # 상하좌우로 이동해보고
        for dy, dx in move:
            my, mx = y+dy, x+dx
            # 이동할 수 있다면
            if 0 <= my < N and 0 <= mx < N:
                # 거리(비용) 비교를 해본다. 갱신이 가능하다면 갱신하고 큐에추가
                if distance[my][mx] > distance[y][x] + field[my][mx]:
                    distance[my][mx] = distance[y][x] + field[my][mx]
                    queue.append((my, mx))
 
 
for t in range(int(input())):
    # 필드 크기
    N = int(input())
    # 필드 입력
    field = [list(map(int, list(input()))) for _ in range(N)]
    # 초기 거리는 무한대로 놓는다.
    INF = float('inf')
    distance = [[ INF for _ in range(N)] for _ in range(N)]
    # 처음 시작부분은 0으로 설정
    distance[0][0] = 0
    # 디큐만들고 처음좌표를 넣어준다.
    queue = deque()
    queue.append((0, 0))
    # 알고리즘 돌려서 거리를 계산한다.
    dijkstra(queue)
    # 결과출력
    print('#{} {}'.format(t+1, distance[N-1][N-1]))

 

# D4 1249 보급로
import heapq
 
# 상하좌우 이동계산용
move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
 
# 다익스트라 알고리즘 계산 함수
def dijkstra(queue):
    # 큐가 빌때까지 반복
    while queue:
        # 좌표를 꺼내서
        d, y, x = heapq.heappop(queue)
        # 상하좌우로 이동해보고
        for dy, dx in move:
            my, mx = y+dy, x+dx
            # 이동할 수 있다면
            if 0 <= my < N and 0 <= mx < N:
                # 거리(비용) 비교를 해본다. 갱신이 가능하다면 갱신하고 큐에추가
                temp = d + field[my][mx]
                if distance[my][mx] > temp:
                    distance[my][mx] = temp
                    if my == N-1 and mx == N-1:
                        return
                    heapq.heappush(queue, (temp, my, mx))
 
for t in range(int(input())):
    # 필드 크기
    N = int(input())
    # 필드 입력
    field = [list(map(int, list(input()))) for _ in range(N)]
    # 초기 거리는 무한대로 놓는다.
    INF = float('inf')
    distance = [[ INF for _ in range(N)] for _ in range(N)]
    # 처음 시작부분은 0으로 설정
    distance[0][0] = 0
    # 디큐만들고 처음좌표를 넣어준다.
    queue = []
    heapq.heappush(queue, (0, 0, 0))
    # 알고리즘 돌려서 거리를 계산한다.
    dijkstra(queue)
    # 결과출력
    print('#{} {}'.format(t+1, distance[N-1][N-1]))