SWEA 1249. [S/W 문제해결 응용] 4일차 - 보급로 (Python, BFS, D4)

SWEA 1249 보급로 문제 바로가기

문제 접근

보자마자 BFS다! 라고 외칠 수 있던 문제였다.
따라서 BFS로 풀어가는 도중에 문제를 잘못보고 최소거리에서, 최소의 시간으로 풀어버렸다... 그래서 왜 안되지... 하면서 DP로도 풀고 BFS로도 풀었다..
결국 둘 다 똑같이 안되고 문제를 다시 본 뒤에서야 풀 수 있었다.

결국 상하좌우 모두로 움직일 수 있기 때문에 BFS로 푸는것이 맞겠다고 생각했다. DP로는 우,좌로 움직일 경우에만 풀 수 있기에, BFS로 풀었다.

문제 풀이

BFS

dx와 dy에 우하상좌의 벡터를 넣어주고 하나의 좌표에서 4가지 방향을 확인하는 구도이다.
확인해야할것은 이번에는 방문했었는지가 아니라 더 최소시간을 가져왔는가?이다.
따라서 이렇게 해서 완전탐색을 하면 result[N-1][N-1]에 최소시간이 담겨있게 된다.

    dx = [0,1,-1,0]
    dy = [1,0,0,-1]
def bfs(a, b):
        q = deque()
        q.append((a,b))
        result[a][b]=0
        while q:
            x,y = q.popleft()
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
                if nx<0 or ny<0 or nx>=N or ny>=N:
                    continue
                if result[x][y]+pan[nx][ny] < result[nx][ny]: 
                    result[nx][ny] = result[x][y]+pan[nx][ny]
                    q.append((nx,ny))

제출 코드

from collections import deque
T = int(input())
for test_case in range(1, T + 1):
    # BFS
    N = int(input())
    pan = []
    for i in range(N):
        line = list(map(int, list(input())))
        pan.append(line)
    result = [[float('inf') for i in range(N)] for j in range(N)]
    dx = [0,1,-1,0]
    dy = [1,0,0,-1]
    def bfs(a, b):
        q = deque()
        q.append((a,b))
        result[a][b]=0
        while q:
            x,y = q.popleft()
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
                if nx<0 or ny<0 or nx>=N or ny>=N:
                    continue
                if result[x][y]+pan[nx][ny] < result[nx][ny]: 
                    result[nx][ny] = result[x][y]+pan[nx][ny]
                    q.append((nx,ny))
    bfs(0,0)
    print(f'#{test_case} {result[N-1][N-1]}')