[python] SWEA - 1249. [S/W 문제해결 응용] 4일차 - 보급로
문제 해결
1. D4 | BFS
2. 각 지점에서 걸리는 시간 리스트(인풋 값)와, 각 지점까지 가는데 걸리는 누적 시간 리스트를 가지고 시작한다.
3. 전에 방문 여부와 상관없이 각 지점에서 상하좌우 4방향을 탐색하며, 현재까지 걸린 시간과 다음칸에서 소모할 시간을 더한 값이 다음 칸까지 걸리는 시간보다 작으면 그 칸으로 이동한다.
4. 모든 가능성을 다 탐색하고 리스트의 마지막지점을 출력한다.
🐱💻 원래는 다익스트라 알고리즘으로 힙큐를 사용해서 풀려고 했는데 생각이 안나서 BFS 랑 최솟값 리스트를 활용해서 풀었다.
소스 코드
from _collections import deque
for tc in range(1, 1 + int(input())):
n = int(input())
maps = [list(map(int, list(input()))) for _ in range(n)]
answer = 0
# keys: 최소값을 누적할 리스트
# 각 지점은 그 지점까지 오는데 드는 시간을 누적
keys = [[99999] * n for _ in range(n)]
keys[0][0] = 0 # 시작점은 0
q = deque()
q.append((0, 0))
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
while q:
x, y = q.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < n and 0 <= ny < n:
# 현재 지점의 값 + 다음 지점을 가는데 필요한 값 < 다음 지점의 값
# 을 비교한다.
if keys[x][y] + maps[nx][ny] < keys[nx][ny]:
keys[nx][ny] = keys[x][y] + maps[nx][ny]
q.append((nx, ny))
answer = keys[-1][-1]
print('#{} {}'.format(tc, answer))
출처: SW Expert Academy
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
|
2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다.
그림 1 (a) 파손된 도로 (b) 지도 형태와 이동 방향 지도 정보는 그림1(b)와 같이 2차원 배열 형태로 표시된다. 출발지는 좌상단의 칸(S)이고 도착지는 우하단의 칸(G)가 된다. 이동 경로는 상하좌우 방향으로 진행할 수 있으며, 한 칸씩 움직일 수 있다. 지도 정보에는 각 칸마다 파여진 도로의 깊이가 주어진다. 현재 위치한 칸의 도로를 복구해야만 다른 곳으로 이동할 수 있다.
이동하는 시간에 비해 복구하는데 필요한 시간은 매우 크다고 가정한다. 따라서, 출발지에서 도착지까지 거리에 대해서는 고려할 필요가 없다. 지도 정보는 그림2에서 보듯이 2차원 배열의 형태이다. 출발지(S)와 도착지(G)는 좌상단과 우하단이 되고 입력 데이터에서는 0으로 표시된다. 출발지와 도착지를 제외한 곳이 0인 것은 복구 작업이 불필요한 곳이다. 다음과 같은 지도에서 복구 작업 시간이 최소인 시간은 2이고 회색으로 칠해진 경로가 된다.
[입력] 가장 첫 줄은 전체 테스트케이스의 수이다. 각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다. 그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다. [출력] 각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다. 같은 줄에 빈 칸을 하나 두고, 주어진 입력에서 출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오. |