[BOJ / 백준] 14940 쉬운 최단거리 python / 파이썬 bfs

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

14940번: 쉬운 최단거리

---

1) 요구사항 분석 : 문제 읽기

각 지점에서 목표지점까지의 거리

 

2) 설계 : 접근 방식

델타탐색 후 2차원 배열의 범위 안에 들어있는지 체크하는 함수를 만들어줌

bfs 함수를 만들어주는데 두번째 반복문을 종료할때마다 x의 크기를 +1 해줌

 

bfs 종료 후 기존의 1(땅)인데 방문처리 안되어 있는 부분은 -1로 바꿔줌

# BOJ14940 쉬운 최단거리
from collections import deque

que = deque()
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
ans = [[0 for _ in range(m)] for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

def bfs(x):
    global que
    while len(que) > 0:
        size = len(que)
        for _ in range(size):
            tem = que.popleft()

            for i in range(4):
                ni = di[i] + tem[0]
                nj = dj[i] + tem[1]
                if in_range(ni, nj) and arr[ni][nj] == 1 and visited[ni][nj] == False:
                    ans[ni][nj] = x
                    visited[ni][nj] = True
                    que.append([ni, nj])
                elif in_range(ni, nj) and arr[ni][nj] == 0 and visited[ni][nj] == False:
                    ans[ni][nj] = 0
                    visited[ni][nj] = True
                    
        x += 1
    

# 2가 목표지점이니까 2부터 시작해서 각 자리가 몇개 떨어져있는지
for i in range(n):
    for j in range(m):
        if arr[i][j] == 2:
            que.append([i, j])
            visited[i][j] = True
            ans[i][j] = 0
            bfs(1)
            break

# bfs
for i in range(n):
    for j in range(m):
        if visited[i][j] == False and arr[i][j] == 1:
            ans[i][j] = -1

for i in range(n):
    print(*ans[i])