[SWEA] 1249. 보급로 (Python)

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

SW Expert Academy

 

1️⃣ 출발지 S(0, 0)에서 도착지 G(N-1, N-1)까지 가장 빠른 시간 안에 복구 완료하기

2️⃣ 도로가 파여진 깊이에 비례하여 복구 시간 소요 ex) 1 ➡️ 1 소요

3️⃣ 0 ➡️ 복구 불필요 (그냥 더해주기)

 

from collections import deque

def bfs():
    q = deque()
    q.append((0, 0))
    while q:
        ny, nx = q.popleft()
        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for i in range(4):
            dy = direct[i][0]+ny
            dx = direct[i][1]+nx
            if 0 <= dy < N and 0 <= dx < N:
                if visit[dy][dx] == 0: # 한 번도 들른 적 없으면
                    visit[dy][dx] = 1
                    spend[dy][dx] = spend[ny][nx]+int(arr[dy][dx]) # 시간 등록
                    q.append((dy, dx))
                else: # 들른 적 있으면
                    if spend[dy][dx] > spend[ny][nx]+int(arr[dy][dx]): # 최소 갱신
                        spend[dy][dx] = spend[ny][nx]+int(arr[dy][dx])
                        q.append((dy, dx))

t = int(input())

for tc in range(1, t+1):
    N = int(input())
    arr = [list(input()) for _ in range(N)]
    visit = [[0]*N for _ in range(N)]
    spend = [[0]*N for _ in range(N)]
    visit[0][0] = 1
    bfs()
    print(f'#{tc} {spend[N-1][N-1]}')

 

✏️ 메모

• 습관처럼 split() 썼다가 안 되길래 봤더니 01234 이런 식으로 붙어 있었다...🙃
• 최소 시간이길래 생각없이 BFS로 풀었더니 답이 제대로 나오지 않았다..ㅠ
• 그럼 DFS로 풀어볼까? 했더니 답은 잘 나오는데 시간 초과🥲
• 구글링의 도움을 받아 각 블록마다 복구에 소요되는 시간을 적어줄 spend배열을 만들어 주었고, visit 배열을 사용해서 한 번도 들른 적 없으면 1 체크 후 spend 배열에 등록 & q에 넣어주기, 들른 적 있으면 spend 배열 최솟값 갱신 후 q에 넣어주는 식으로 했다.
• 도착지는 (N-1, N-1) 이므로 spend 배열의 (N-1, N-1) 값을 출력해주면 정답이다.