[14940] 쉬운 최단거리

문제 이해

1이면 가고 2면 출발 0이면 벽임
못 도달 하는 곳은 -1로 출력 해야함 
그럼 모든 곳을 -1로 초기화하고 나머지는 거리를 이전거리에서 하나씩 더하면 될 것 같음
출력 예시 보니까 bfs인 것 같음. 입력값보니까 dfs하면 어차피 시간초과임

========================================
코드 계획

입력 받기 
N, M 저장
N 번 반복하면서 입력 받는데 2부터 탐색 해야 하니까 저장(x,y)

네방향 이동할 dx, dy 리스트 생성

-1로 초기화한 answer 배열 생성
방문 여부 visited 배열은 False로 초기화

큐에 2의 x,y좌표 저장
방문처리
answer 처음위치 0으로 정하기

q가 비어있지 않을 동안 반복
curx, cury에 q pop해서 저장
네 방향 반복하면서 nx, ny 저장
만약 맵 안인가? 1인가?(갈 수 있는가?) 아직 방문 안했는가?
그럼 큐에 넣기
방문처리
answer nx ny에 현재 위치 값 + 1해서 저장하기 

 

import sys

from collections import deque;

input = sys.stdin.readline

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

graph = []

for i in range(n):

    li = input().strip().split()

    if '2' in li:

        x = i

        y = li.index('2')

    li = list(map(int, li))

    graph.append(li)

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

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

answer = [[-1]*m for _ in range(n)]

visited = [[False]*m for _ in range(n)]

q = deque([(x,y)])

visited[x][y] = True

answer[x][y]=0

while q:

    cx, cy = q.popleft()

    for i in range(4):

        nx = cx + dx[i]

        ny = cy + dy[i]

        if 0 <= nx < n and 0 <= ny < m:

            if graph[nx][ny] == 1:

                if visited[nx][ny] == False:

                    q.append((nx,ny))

                    visited[nx][ny] = True

                    answer[nx][ny] = answer[cx][cy] + 1

                   

for i in range(n):

    for j in range(m):

        if graph[i][j] == 0:

            print(0, end=' ')

        else:

            print(answer[i][j], end=' ')

    print()