[파이썬] SWEA - 보급로

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

SW Expert Academy

보급로 문제

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}')