[SWEA 1249번] 파이썬 - 보급로

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

SW Expert Academy

 

 

# 조건

• 위 그림처럼 도로 곳곳이 파손되어 있다.
• 복구하기 위한 공병대는 상하좌우로 이동 가능하며, S(0,0)에서 G(N-1,N-1)까지 복구 작업을 하는데 가장 빠른 시간 내에 수행한다.
• 깊이 1에 시간 1이 걸리며 한 칸씩 움직일 수 있다.

 

 

# 접근 방법

• 최단 경로 알고리즘이다.
• 다익스트라 알고리즘을 사용하며, heapq 대신 BFS를 함께 사용해주어도 될 것 같다.
• 내가 갈 좌표에 대해, 좌표의 현재 값과, 지금 들어갈 값을 비교하며 갱신해주고,
• 갱신 좌표를 q에 넣어주는 식으로 G까지 도달하면 될 것 같다.

# S에서 G까지 가기 위해 도로 복구 작업
# 파여진 깊이에 비례하여 복구 시간 증가
# 복구 시간이 가장 짧은 경로에 대해 복구 시간 구하라
# 깊이 1 == 시간 1

from collections import deque
import sys
sys.stdin = open('input.txt')

def bfs(start):
    q = deque()
    # q에 시작위치 넣어주고
    q.append(start)
    di, dj = [1, -1, 0, 0], [0, 0, 1, -1]
    while q:
        sti, stj = q.popleft()
        for k in range(4):
            dx, dy = sti + di[k], stj + dj[k]
            # 이동가능한 곳이라면
            if 0<=dx<N and 0<=dy<N:
                # 거리 비교하여 최소라면 갱신해주고 큐에 추가.
                if repair[dx][dy] > repair[sti][stj] + road[dx][dy]:
                    repair[dx][dy] = repair[sti][stj] + road[dx][dy]
                    q.append((dx,dy))

    return repair

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    # 현재 도로 리스트
    road = [list(map(int, list(input()))) for _ in range(N)]
    # 수리하며 지나갈 리스트
    repair = [[100000] * N for _ in range(N)]
    # 시작위치는 0으로 바꿔준다.
    repair[0][0]=0

    bfs((0,0))

    print(f'#{tc} {repair[-1][-1]}')

 

 

다른 분들의 코드를 보다가 heapq와 priority queue를 사용한 분들이 있어 참고해보면 될 것 같다.

 

# heapq

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]))

 

# priority queue

# D4 1249 보급로 - PriorityQueue
from queue import PriorityQueue
 
# 상하좌우 이동계산용
move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
 
# 다익스트라 알고리즘 계산 함수
def dijkstra(queue):
    # 큐가 빌때까지 반복
    while queue.qsize():
        # 좌표를 꺼내서
        d, y, x = queue.get()
        # 상하좌우로 이동해보고
        for dy, dx in move:
            my, mx = y+dy, x+dx
            # 이동할 수 있다면
            if 0 <= my < N and 0 <= mx < N:
                # 거리(비용) 비교를 해본다. 갱신이 가능하다면 갱신하고 큐에추가
                if distance[my][mx] > d + field[my][mx]:
                    distance[my][mx] = d + field[my][mx]
                    if my == N-1 and mx == N-1:
                        return
                    queue.put((distance[my][mx], 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 = PriorityQueue()
    queue.put((0, 0, 0))
    # 알고리즘 돌려서 거리를 계산한다.
    dijkstra(queue)
    # 결과출력
    print('#{} {}'.format(t+1, distance[N-1][N-1]))

 

[참고] https://mungto.tistory.com/224

• 아직 다익스트라 알고리즘과 heapq에 대해 많이 알지 못하여서 공부가 필요할 것 같다!