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

코드

## SWEA 1249
from collections import deque
T = int(input())
move = [ (1,0), (0,-1),(-1,0),(0,1) ]
def bfs():
    global result
    queue = deque()
    queue.append((0,0))
    dist_arry[0][0] = 0

    while queue:
        x,y = queue.popleft()
        for dx,dy in move :
            nx = x + dx
            ny = y + dy
            if 0<= nx < N and 0 <= ny < N :
                dist = dist_arry[x][y] + arry[nx][ny]
                if dist < dist_arry[nx][ny] :
                    dist_arry[nx][ny] = dist
                    queue.append((nx,ny))

for test_case in range(1, T + 1):
    N = int(input())
    arry = [ [ int(i) for i in list(input())] for _ in range(N) ]

    dist_arry = [ [float("inf")]*N for _ in range(N) ]
    bfs()
    result = dist_arry[N-1][N-1]
    print(f"#{test_case} {result}")

 

풀이

처음에는 단순히 BFS로 완전 탐색을 하려고 도전했으나.. test case 3개만 맞고 time error가 발생했다. 

그래서 DP개념을 좀 넣어서 dist_arry를 업데이트하며 가지치기를 해서 time error를 없앨 수 있었다.

 

 

 

아래는 time error가 발생한 코드..

너무 습관적으로 visited arry를 만들어 쓰는 경향이 있는 것 같다. 

## SWEA 1249
from collections import deque

T = int(input())
move = [(1, 0), (0, -1), (-1, 0), (0, 1)]


def bfs():
    global result
    queue = deque()
    queue.append((0, 0, 0))

    while queue:
        x, y, dist = queue.popleft()
        visited[x][y] = 1

        if x == N - 1 and y == N - 1:
            if result > dist:
                result = dist

        for dx, dy in move:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
                queue.append((nx, ny, dist + arry[nx][ny]))


for test_case in range(1, T + 1):
    N = int(input())
    arry = [[int(i) for i in list(input())] for _ in range(N)]
    visited = [[0] * N for _ in range(N)]
    result = float("inf")
    bfs()
    print(f"#{test_case} {result}")