보급로

[ramge132]

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AZC_w6Z6yygDFAQW&contestProbId=AV15QRX6APsCFAYD&probBoxId=AZDJUP6q-f0DFAVs&type=PROBLEM&problemBoxTitle=5d_practice&problemBoxCnt=2

[ImJongHoon]

from collections import deque
import sys
sys.stdin = open("input.txt", "r")

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.

dy = [-1,0,1,0]
dx = [0,1,0,-1]

visited = []

def print_board(board):
    for li in board:
        print(li)
    print()
    print()
def BFS(board, start_y, start_x, size):
    visited[start_y][start_x] = board[start_y][start_x]
    q = deque([(start_y, start_x)])
    #print(board)

    while q:
        (y, x) = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if ny < 0 or nx < 0 or ny >= size or nx >= size:
                continue
            #print(board[ny][nx])

            if visited[ny][nx] <= visited[y][x] + board[ny][nx]:#가봤자 많으면
                continue
            else:
                q.append((ny, nx))

                visited[ny][nx] = visited[y][x] + board[ny][nx]
                print_board(visited)

    return
def main():
    for test_case in range(1, T + 1):
        num = int(input())
        board = [list(map(int, list(input()))) for _ in range(num)]

        global visited
        visited = [[987654321]*num for _ in range(num)]

        BFS(board, 0, 0, num)

        print(f"#{test_case} {visited[num-1][num-1]}")

if __name__ == "__main__":
    main()

[seokbangguri]

보급로 거의 경부고속도로

from collections import deque
# 우, 하, 상, 좌
dxy = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def bfs():
    while len(Q):
        x, y = Q.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy

            # 매트릭스의 레인지를 넘어가는 경우 진행 X
            n = len(matrix)
            if nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1:
                continue

            # 현재 탐색의 작업 시간
            cur_min_val = min_val_matrix[y][x] + matrix[ny][nx]

            # 해당 위치까지 최소 시간이 아니면 진행 X (가지치기)
            if min_val_matrix[ny][nx] <= cur_min_val:
                continue
            # 최단 시간 일 경우
            else:
                # 큐에 추가
                Q.append((nx, ny))
                # 최단 시간 업데이트
                min_val_matrix[ny][nx] = cur_min_val

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N = int(input())
    matrix = [list(map(int, input())) for _ in range(N)]
    min_val_matrix = [[float('inf')] * N for _ in range(N)]
    Q = deque([(0, 0)])
    min_val_matrix[0][0] = matrix[0][0]
    bfs()
    print(f'#{test_case} {min_val_matrix[-1][-1]}')
    # ///////////////////////////////////////////////////////////////////////////////////

[taromilktea00]

from collections import deque

def bfs(x, y):
    global map_board, visited
    global map_size

    q = deque([(x, y)])

    dxy = [[0, -1], [-1, 0], [1, 0], [0, 1]]
    visited[y][x] = map_board[y][x]
    while q:
        now_x, now_y = q.popleft()
        for dx, dy in dxy:
            next_x = now_x + dx
            next_y = now_y + dy
            # 다음에 갈 곳이 배열 안에 있으면
            if 0 <= next_x < map_size and 0 <= next_y < map_size:
                new_value = visited[now_y][now_x] + map_board[next_y][next_x]
                if visited[next_y][next_x] == -1 or new_value < visited[next_y][next_x]:
                    q.append((next_x, next_y))
                    visited[next_y][next_x] = new_value
            # 다음에 방문할 곳이 배열 인덱스 초과했을 경우
            else:
                continue

test_case = int(input())

for t in range(1, test_case+1):

    map_size = int(input())
    map_board = [list(map(int, input())) for _ in range(map_size)]
    visited = [[-1 for j in range(map_size)] for i in range(map_size)]
    bfs(0, 0)
    print(f'#{t} {visited[map_size-1][map_size-1]}')