[Python] [SWEA] 보급로(1249)

💡 문제 해결

1. 방문 여부를 확인하기 위한 리스트 생성
2. 복구 시간을 저장하기 위한 리스트 생성
3. bfs 탐색 중 출발지로 돌아가는 경우 제외
4. 처음 방문하는 곳이면 (현재까지의 시간 + 탐색 방향의 시간) 지정 후 stack에 추가
5. 이미 방문했던 곳이라면 이미 할당된 값과 비교하여 작은 값 갱신 후 stack에 추가
6. 도착점의 시간 출력

📌 다익스트라로 풀어보려 했지만 익숙하지 않아 bfs로 풀이 진행..
📌 방문 리스트 초기값을 최대값으로 설정해두면 5번과 6번의 과정을 하나로 단축 가능

🧾 문제 설명

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

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

문제보기

🖨 입출력

📝 풀이

from collections import deque

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def bfs(arr, visited, time, S, G):
    deq = deque([S])
    while deq:
        x, y = deq.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < N:
                if nx == 0 and ny == 0: continue
                elif visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    time[nx][ny] = time[x][y] + arr[nx][ny]
                    deq.append((nx, ny))
                else:
                    if time[nx][ny] > time[x][y] + arr[nx][ny]:
                        time[nx][ny] = time[x][y] + arr[nx][ny]
                        deq.append((nx, ny))



for tc in range(1, int(input()) + 1):
    N = int(input())
    arr = list(list(map(int, input())) for _ in range(N))

    visited = [[0] * N for _ in range(N)]
    time = [[0] * N for _ in range(N)]
    S, G = [0, 0], [N - 1, N - 1]
    
    bfs(arr, visited, time, S, G)
    answer = time[G[0]][G[1]]
    
    print(f'#{tc} {answer}')

• 출처: SW Expert Academy
• 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE