Python으로 푸는 SW Expert Academy 1249. 보급로

SW Expert Academy 1249 보급로

이 문제는 파괴된 도로를 지나갈 수 없는 트럭이나 탱크가 

도착 지점까지 가장 빠른 시간안에 도착할 수 있도록

최단 시간 경로를 찾아 파괴된 도로를 수리하여야 한다.

얼마나 걸려야 시작지점에서 도착지점에 가장 빨리 도착할 수 있을까.

SW Expert Academy에서 푼 문제 보기

github에서 코드 보기

문제 조건

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

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

시간이 적다면 길을 돌아가도 상관 없다. (상하좌우로 이동 가능)

문제를 틀렸다면 생각할 상황 

길을 돌아가는게 오히려 시간을 절약할 수도 있다. 

1

6

010000

010100

010100

010100

010100

000100

output : 0

문제 풀이

문제 자체는 복잡해 보이는데 결국 시작점에서 도착지점까지 최소 비용 거리를 구하는 문제이다.

visited 2차원 배열을 만들어서 각 지점마다 최소 비용으로 갈 수 있는 비용을 기록해둔다.

시작 지점에서부터 상하좌우로 나아갈 수 있는 주변 지점에 도착할 때 필요한 비용을 계산한다.

이미 다른 지점에서 주변 지점과의 비용을 계산했을 때의 비용이 visited에 남아있다면 

더 최소 비용인 경우를 다시 기록해주고, 그 지점부터 최소 비용을 다시 탐색하기 위해서 '다시 탐색할 지점 리스트'(checkList) 안에 넣어준다. 

이 작업을 모두 반복하여 더 이상 체크할 지점이 없을 경우 visited에 기록된 도착 지점의 값을 반환해주면 된다.

파이썬 코드

 
from collections import deque
 
def solve(n, lines):
    visited = [[-1]*n for i in range(n)]
    checkList = deque([(0, 0)])
    visited[0][0] = lines[0][0]
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while checkList:
        x, y = checkList.popleft()
        if x == n-1 and y == n-1:
            continue
        current_v = visited[x][y]
        for i in range(4):
            temp_x = x + dx[i]
            temp_y = y + dy[i]
 
            # 범위 초과
            if temp_x < 0 or temp_y < 0 or temp_x >= n or temp_y >= n:
                continue
            # 첫 비용 계산이거나, 기록된 비용보다 최소 비용일 
            if visited[temp_x][temp_y] == -1 or \
                current_v + lines[temp_x][temp_y] < visited[temp_x][temp_y]:
                visited[temp_x][temp_y] = current_v + lines[temp_x][temp_y]
                checkList.append((temp_x, temp_y))
 
    return visited[n-1][n-1]
 
 
if __name__ == "__main__":
    t = int(input().strip())
    for tc in range(1, t+1):
        n = int(input().strip())
        lines = []
        for i in range(n):
            line = list(map(int, list(input().strip())))
            lines.append(line)
        print("#{0} {1}".format(tc, solve(n, lines)))
 
 

#1249. 보급로 #sw expert 보급로 #sw expert 1249 보급로 #python 1249 보급로 #파이썬 1249 보급로