[파이썬, Python] 백준 14940: 쉬운 최단거리

문제

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

14940번: 쉬운 최단거리

코드

from collections import deque

n, m = map(int, input().split())

#땅, 거리 설정
land = [list(map(int, input().split())) for _ in range(n)]
dis = [[0] * m for _ in range(n)]

dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

#bfs 세팅            
def bfs(i, j):
    q = deque()
    q.append((i, j))
    
    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m and dis[nx][ny] == 0 and land[nx][ny] == 1:
                dis[nx][ny] = dis[x][y] + 1
                q.append((nx, ny))

#시작 위치 찾기                
for i in range(n):
    for j in range(m):
        if land[i][j] == 2:
            bfs(i, j)

#도달하지 못한 땅 처리            
for i in range(n):
    for j in range(m):
        if land[i][j] == 1 and dis[i][j] == 0:
            dis[i][j] = -1

#출력 형식 맞추기
for i in range(n):
    for j in range(m):
        print(dis[i][j], end = ' ')
    print()

설명

bfs를 통해서 해결이 가능한 문제였다.

우선 간단하게 지도를 입력받아주고 거리를 표시할 dis도 생성해 준다.

그리고 bfs를 정의해 준다.
deque를 이용하여 popleft 하며 진행하고
범위가 벗어나지 않고, 거리가 0이며(방문 X), 땅은 1인 숫자에 한해 진행한다.
해당 땅의 거리는 이전 거리에 1을 더한 수로 세팅해 주고
좌표를 큐에 넣어준다.

시작 위치는 지도의 좌표 중 2의 값을 가진 위치에서 시작한다.

bfs가 완료된 후 땅이지만 도달하지 못한 좌표의 값을 -1로 처리해 준다.

이후 출력 형식에 맞춰 출력한다.