[python]14940_쉬운 최단거리

사용한 자료구조 및 개념 : bfs

 

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

1️⃣ 거리를 체크하기 위한 새로운 이차원리스트 distance를 만든다.

2️⃣ 원래 갈 수 없는 곳은 0 그대로 출력해야하고 갈 수 있는 땅(1)이나 목표지점까지 도달할 수 없는 위치는 -1을 출력해야하기 때문에 갈 수 있는 땅은 distance에서 초기값을 -1로 설정한다.

3️⃣ 목표지점에서 출발한다!

4️⃣ 이동 가능한 범위 내에서 갈 수 있는 곳이고, 방문하지 않았던 곳이라면 이동한다.

 

 

---

 

Solution Code & 주석

import sys
from collections import deque

input = sys.stdin.readline

def bfs(x, y):
    queue = deque([(x, y)])
    distance[x][y] = 0

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

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx = x + dx
            ny = y + dy
            if (
                0 <= nx < n
                and 0 <= ny < m
                and board[nx][ny] == 1  # 1로 설정하면 갈 수 없는 곳은 안가고 목적지이면 안가게됨
                and distance[nx][ny] == -1  # 방문하지 않은 지점 확인 조건
            ):
                distance[nx][ny] = distance[x][y] + 1
                queue.append((nx, ny))

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
distance = []

for row in board:
    new_row = []
    for cell in row:
        if cell != 0:
            new_row.append(-1)
        else:
            new_row.append(0)
    distance.append(new_row)

for i in range(n):
    for j in range(m):
        if board[i][j] == 2:
            gx, gy = i, j
            break

bfs(gx, gy)

for line in distance:
    print(*line)