[백준] 14940번 쉬운 최단거리

💡문제접근

• 목표지점 2가 나오는 행렬의 좌표에서 BFS 탐색을 진행하여 만약 0이 나오면 0 그대로 출력을 하고 만약 주변이 다 0으로 둘러싸여 있어서 진출할 수 없어 다른 좌표에 도달하지 못하면 -1을 출력해야한다. 방문여부를 탐색하는 배열과 지도를 나타내는 배열, 그리고 각 지점에서 목표지점까지의 거리를 나타내는 배열 총 3개를 사용해서 문제를 해결했다.

💡테스트케이스

입력

3 3
2 0 1
0 1 1
1 1 1

출력

0 0 -1
0 -1 -1
-1 -1 -1

💡코드(메모리 : 41720KB, 시간 : 572ms)

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().strip().split())
# 주어지는 지도
graph = []
for _ in range(n):
    graph.append(list(map(int, input().strip().split())))
# 확인 완료

visited = [[False] * m for _ in range(n)]
result = [[-1] * m for _ in range(n)]
# 확인 완료

def BFS(a, b):
    queue = deque()
    queue.append((a, b))
    while queue:
        x, y = queue.popleft()
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx = x + dx[i]    # 가로
            ny = y + dy[i]    # 세로
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and graph[nx][ny] == 1:
                queue.append((nx, ny))
                visited[nx][ny] = True
                result[nx][ny] = result[x][y] + 1

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            visited[i][j] = True
            x, y = i, j
            result[i][j] = 0

        if graph[i][j] == 0:
            result[i][j] = 0

BFS(x, y)
for i in result:
    for j in i:
        print(j, end = " ")
    print()

💡소요시간 : 30m