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

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

1. 문제

요약하자면 목표지점에서 모든 지점까지의 거리를 구하는문제이다.

2. 풀이

목표지점으로부터의 거리를 구하는 문제이므로 BFS를 사용하였다. BFS를 구현하기 위해 파이썬의 deque을 사용하였다.

(1)BFS(너비 우선탐색)

BFS는 시작지점을 방문한 후 인접한 모든 점을 우선적으로 방문하는 방법이다.

(2)Deque(덱)

queue와는 다르게 양방향으로 입/출력이 가능한 자료구조이다.

 

3. 코드

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


n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[-1] * m for _ in range(n)]

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


def bfs(i, j):
    queue = deque()
    queue.append((i, j))

    visited[i][j] = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i]+x, dy[i]+y
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == -1:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = 0
                elif graph[nx][ny] == 1:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))


for i in range(n):
    for j in range(m):
        if graph[i][j] == 2 and visited[i][j] == -1:
            bfs(i, j)

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            print(0, end=' ')
        else:
            print(visited[i][j], end=' ')
    print()

방문하지 않은 지점은 -1로 설정하여 방문하지 않았으며 시작지점이 2인 좌표에서 시작한다.

bfs를 이용하여 방문할 수 있는 곳의 거리를 계산하여 visited에 입력해준 후 출력한다.