[파이썬/python] SWEA - 보급로

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

---

문제 설명

1. 출발지 S에서 도착지 G까지 이동하며 도로 복구 작업을 진행하려고 한다.
   1. S: (0,0)
   2. G: (N-1,N-1)
2. 도로는 파여진 깊이에 비례해서 복구 시간이 증가한다.
   1. 깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다.
3. 출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구시간을 구한다.

 

---

풀이

결국에는 S에서 G로 이동할 때 최소 비용을 구하는 것이 이 문제의 핵심이다.

 

다익스트라를 통해 최소 비용을 구하면 풀리는 문제였다.

이 문제는 2차원 배열이 주어졌기 때문에 다익스트라 알고리즘이 아닌 BFS를 통해 최단 거리를 매번 갱신하면서 도착지점으로 이동하도록 코드를 구현했다.

 

전체적인 로직은 BFS와 동일하다.

 

하지만 다른점은 방문 배열 대신 거리 배열을 사용하고, 다음 좌표로 이동할 때 현재 갱신하려는 거리보다 최단거리라면 탐색을 진행하지 않는 다는 것이다.

 

if dist[ny][nx] <= dist[y][x] + board[y][x] 라면 갱신 X

 

그렇기 때문에 BFS지만 다익스트라처럼 동작하도록 해서 최단거리를 구할 수 있었다.

---

코드

from collections import deque
 
INF = int(1e9)
dy = [0,1,0,-1]
dx = [1,0,-1,0]
def bfs():
    queue = deque([(0,0)])
 
    while queue:
        y,x = queue.popleft()
 
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or ny > N-1 or nx < 0 or nx > N-1 or dist[ny][nx] <= dist[y][x]+board[ny][nx]:
                continue
            dist[ny][nx] = dist[y][x] + board[ny][nx]
            queue.append((ny,nx))
     
for tc in range(1,int(input())+1):
    N = int(input())
    board = [list(map(int,input().strip())) for _ in range(N)]
    board[0][0] = INF
    dist = [[INF for _ in range(N)] for _ in range(N)]
    dist[0][0] = 0
     
 
    bfs()
    print(f'#{tc} {dist[-1][-1]}')

---

시간복잡도

• 최악의 경우 $N = 100$이다. 따라서 최악의 경우 $O(10^4)$ 정도의 시간복잡도가 소요된다.