[백준]14940. 쉬운 최단거리/Python - Silver1

❓문제

https://www.acmicpc.net/problem/14940

성능 요약

메모리: 41932 KB, 시간: 488 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

✍🏻풀이

이 문제는 BFS이다. 문제에서 2는 목표지점이다. 그리고 우리가 구해야 하는 것은 각 갈 수 있는 땅 위에서 목표지점까지의 거리를 구하는 것이다. 그러므로 출발지를 목표지점으로 두면 된다.

목표지점이 정확히 (0, 0)에서 주어진다는 보장이 없으므로 우리는 목표지점을 찾아야 한다. 그리고 목표지점을 찾아 각 거리를 계산하면 된다. 이 때, 방문한 곳인지를 표시하는 동시에 거리를 계산하기 위해 visited를 따로 만들어 계산한다.

각 거리의 계산이 끝나면 갈 수 있는 땅이지만 방문하지 않은 곳은 -1로 출력하고 나머지는 visited 값으로 출력하면 된다.

💻코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
dy = [1, 0, 0, -1]
dx = [0, 1, -1, 0]

q = deque()

def bfs(y, x):
    q.append((y, x))
    board[y][x] = 0

    while q:
        y, x = q.popleft()

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

            if 0 <= ny < n and 0<= nx < m and not visited[ny][nx] and board[ny][nx] == 1:
                visited[ny][nx] = visited[y][x] + 1
                q.append((ny, nx))

for y in range(n):
    for x in range(m):
        if board[y][x] == 2:
            bfs(y, x)
            break

for y in range(n):
    for x in range(m):
        if board[y][x] > 0 and not visited[y][x]:
            print(-1, end=' ')
        else:
            print(visited[y][x], end=' ')
    print()

📍후기

bfs 부분을 함수로 따로 빼서 만들었더니 시간이 줄었다. 그런데 메모리는 어떻게 하면 줄일 수 있을까?