[백준/Python] (S1)14940 - 쉬운 최단거리

 

쉬운 최단거리 성공

 

 

14940번: 쉬운 최단거리

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

12940

5209

4230

37.832%

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

예제 입력 1 복사

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력 1 복사

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

너비우선 탐색 문제

시작점이 항상 고정이 아니기 때문에 , 배열을 받아올 때 문제에 나와있는대로 2를 탐색 후 위치를 넣어주고 BFS알고리즘을 적용해준다.

#14940 쉬운 최단거리
import sys
from collections import deque

n, m = map(int,sys.stdin.readline().split())

li = []
x,y = 0,0

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
for _ in range(n):
    s = list(map(int,sys.stdin.readline().split()))
    if 2 in s:
        x,y = _,s.index(2)
        li.append(s)
        li[x][y] = 1
        
    else:
        li.append(s)


def BFS(x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if li[nx][ny] == 0:
                continue
            if li[nx][ny] == 1:
                li[nx][ny] = (li[x][y] + 1)
                queue.append((nx,ny))

BFS(x,y)

for i in range(n):
    for j in range(m):
        if li[i][j] == 1:
            li[i][j] = -1
        elif li[i][j] != 0:
            li[i][j] += -1

li[x][y] = 0

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