[Python]14940번.쉬운 최단거리(그래프 이론,그래프 탐색,BFS)

14940번: 쉬운 최단거리

💡문제

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

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

입력

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

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

출력

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

 

풀이💬

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

# 입력
N, M = map(int, input().split())
list = []
queue = deque([])
visit = [[False]*M for _ in range(N)]
res = [[-1]*M for _ in range(N)]

for i in range(N):
    row = list(map(int, input().split()))

    for j in range(M):
        # 목표지점 찾기
        if row[j] == 2:
            queue.append((i, j))
            visit[i][j] = True
            res[i][j] = 0

        # 벽 기록
        if row[j] == 0:
            res[i][j] = 0
    list.append(row)

# BFS 탐색
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 상하좌우
while queue:
    x, y = queue.popleft()

    for dx, dy in direction:
        nx, ny = x+dx, y+dy

        if 0 <= nx < N and 0 <= ny < M and not visit[nx][ny] and list[nx][ny] == 1:
            queue.append((nx, ny))
            visit[nx][ny] = True
            res[nx][ny] = res[x][y] + 1

# 출력
for row in res:
    for i in row:
        print(i, end=" ")
    print()

→ 런타임 에러 (제일 답답한 이유 ... ) 위와 같이 해결 👏🏻

• 첫 번째 코드는 'sys.stdin.readline()'을 사용하여 각 행을 따로 입력받고, 두 번째 코드는 'sys.stdin.readlin()'을 사용하여 한 번에 모든 행을 입력받는다.

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

direction = [(-1,0),(1,0),(0,-1),(0,1)]
n,m = map(int,input().split())
arr = list(input().split() for _ in range(n))
visited = [[False]*m for _ in range(n)]
ans = [[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if arr[i][j]=="2":
            visited[i][j] = True
            q = deque([(i,j)])

while q:
    x, y = q.popleft()
    for dx, dy in direction:
        nx = x+dx
        ny = y+dy

        if 0<=nx<n and 0<=ny<m and arr[nx][ny]=="1" and not visited[nx][ny]:
            q.append((nx,ny))
            visited[nx][ny] = True
            ans[nx][ny]= ans[x][y]+1

for i in range(n):
    for j in range(m):
        if not visited[i][j] and arr[i][j]=="1":
            print(-1,end=" ")
        else:
            print(ans[i][j], end=" ")
    print()