14940번: 쉬운 최단거리
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이
www.acmicpc.net
문제
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
입력
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.
출력
각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.
코드
from collections import deque
n, m = map(int, input().split())
map_data = []
dist = [[-1] * m for _ in range(n)]
dest_x, dest_y = 0, 0
for i in range(n):
lst = list(map(int, input().split()))
for j in range(m):
if lst[j] == 0:
dist[i][j] = 0
if lst[j] == 2:
dest_x, dest_y = i, j
dist[dest_x][dest_y] = 0
map_data.append(lst)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
visited = [[False] * m for _ in range(n)]
q = deque([[dest_x, dest_y, 0]])
visited[dest_x][dest_y] = True
while q:
x, y, d = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if map_data[nx][ny] == 0:
dist[nx][ny] = 0
if map_data[nx][ny] == 1 and not visited[nx][ny]:
dist[nx][ny] = d + 1
q.append([nx, ny, d+1])
visited[nx][ny] = True
for i in range(n):
print(*dist[i])
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 2636번 치즈 (0) | 2023.06.23 |
---|---|
[Python/파이썬] 백준 5547번 일루미네이션 (0) | 2023.06.23 |
[Python/파이썬] 백준 1600번 말이 되고픈 원숭이 (0) | 2023.06.19 |
[Python/파이썬] 백준 13023번 ABCDE (0) | 2023.04.25 |
[Python/파이썬] 백준 2668번 숫자고르기 (0) | 2023.04.25 |