시작하는 중
[파이썬] SWEA - 보급로 본문
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
보급로 문제
SSAFY 시작 전에 나에게 가장 큰 벽이였던 문제이다.
단순하게 y,x 각각에 대해서 한 방향으로 가는 문제는 다익스트라 비슷하게 풀었지만
이 문제는 4방향으로 갈 수 있다는 점이 다르다.
그림처럼 A1-B1-C1으로 가는 것보다 A1-A2-B2-C2-C1으로 가는게 더 복구 시간이 짧다.
풀이
방법은 많지만 다익스트라로 하기로 했다.
1. 출발지인 0,0을 제외한 모든 항목을 문제의 답의 최대값으로 설정한 NxN 2차원 리스트 visited 생성
2. 0,0부터 델타탐색+BFS로 모든 좌표를 탐색함
2-1. 지금 좌표는 y,x로 하고 이동할 좌표를 ny,nx로 하면 이동할 좌표의 visited[ny][nx]가 지금 현재의 위치 + 입력값에 따른 복구시간보다 크다면 -> 지금 내가 온 경로가 더 짧은 시간을 요구하니 업데이트
3. 모든 탐색이 끝나면 visited[N-1][N-1]을 출력
코드
# 조건문에서 최대는 100X100행렬에 모든 항목이 9가 들어간 경우이다.
INF = 100*100*9
def bfs():
# 다익스트라 알고리즘을 적용하기 위한 배열 생성
visited = [[INF for _ in range(N)] for _ in range(N)]
visited[0][0] = 0
q = [(0,0)] # bfs이니까 큐 형태
d = [(-1,0),(1,0),(0,-1),(0,1)] # 델타 탐색을 위한 배열
# bfs 시작
while q:
y,x = q.pop(0)
for dy,dx in d:
ny = y + dy
nx = x + dx
# ny,nx의 유효성 확인 + 다익스트라 알고리즘
if 0 <= ny < N and 0 <= nx < N and visited[ny][nx] > visited[y][x] + lst[ny][nx]:
visited[ny][nx] = visited[y][x] + lst[ny][nx]
q.append((ny,nx))
return visited[-1][-1]
T = int(input())
for t in range(1,T+1):
N = int(input())
lst = list(list(map(int,input())) for _ in range(N))
answer = bfs()
print(f'#{t} {answer}')
'알고리즘 > SWEA' 카테고리의 다른 글
[파이썬] swea 1767. [SW Test 샘플문제] 프로세서 연결하기 (0) | 2022.10.13 |
---|