Algorithm/백준

백준 14940번 [파이썬]

comoZ 2022. 9. 25. 23:26

최단거리 구하기 문제

당연하게도 DFS로 풀었다.

처음에 while문에 무한반복되면 자동으로 멈추라고 적당히 종료조건 넣었다가.... 까먹고 

"맞는거같은데.. 뭐지?" 하면서 삽질했다...

꾸준히 코딩안한 벌인듯... 

 

from collections import deque

dq= deque([])

n,m= map(int, input().split())
arr=[list(map(int, input().split())) for _ in range(n)]
visit=[[0]*m for _ in range(n)]
result=[[0]*m for _ in range(n)]

def range_out(x,y):
    if x<0 or x>=n or y<0 or y>=m or arr[x][y]==0 or visit[x][y]==1:
        return False
    return True

xs=[1,-1,0,0]
ys=[0,0,1,-1]

for i in range(n):
    for j in range(m):
        if arr[i][j]==2:
            dq.append([i,j])
            visit[i][j]=1
            result[i][j]=0

while dq:
    x,y=dq.popleft()
    for dx,dy in zip(xs,ys):
        r,c=x+dx,y+dy
        if range_out(r,c):
            result[r][c]=result[x][y]+1
            dq.append([r,c])
            visit[r][c]=1

for i in range(n):
    for j in range(m):
        if visit[i][j]==0 and arr[i][j] ==1:
            result[i][j]=-1


for i in range(n):
    print(*result[i])

코드 훈수 환영합니다!!