1249. [S/W 문제해결 응용] 4일차 - 보급로

기본적인 다익스트라, BFS 문제였다. 

 

생각할 점은

• 누적값을 저장할 공간 만들기
• 값이 더 작을 경우에만 큐에 넣기
• 칸 안에 있는 지 검사하기 - valid  함
• python 에서 false 가 아니라 False 임 - 대문자..
• 최대값 쓰고 싶으면 float('inf') 사용하기

def valid(n_x, n_y):
    if n_x < 0 or n_y < 0:
        return False
    if n_x >= N or n_y >= N:
        return False
    return True
    

def bfs(start):
    q = [start]
    min_board = [[float('inf')] * N for _ in range(N)]
    min_board[start[0]][start[1]] = 0
    dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
    while q:
        curr = q.pop(0)
        for i in range(4):
            new_x = curr[0] + dx[i]
            new_y = curr[1] + dy[i]
            if valid(new_x, new_y):
                new_val = min_board[curr[0]][curr[1]] + board[new_x][new_y]
                if new_val < min_board[new_x][new_y]:
                    min_board[new_x][new_y] = new_val
                    q.append((new_x, new_y))
    return min_board[N-1][N-1]
            
        
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    board = []
    for i in range(N):
        board.append([int(x) for x in input()])
    answer = bfs((0, 0))
    print(f'#{test_case} {answer}')