Baekjoon 14940 | 쉬운 최단거리 (Python)

📌문제

SILVER1 / bfs / 그래프이론 / 그래프탐색

https://solved.ac/contribute/14940

📌문제 분석 및 설계

제목 그대로 쉬운 최단거리 구하는 문제이다.

보자마자 뭐야 쉽네 하고 걍 bfs여러번돌렸다가 시간초과나와서

아? 하고 생각하니 걍 도착지점에서 모든 distance를 구하면 되는 거였다.

 

다 푼 후에 코드를 정리하려고 보니,

원래는 2인 지점을 따로 반복문에 넣고 찾은후에 bfs돌리고 도달할 수 없는 위치 처리해줬는데 불필요한 반복이라

우선 이중 반복문을 통해 위에 말한 처리들을 한번에 해주고 그 후에 bfs가 돌아가도록 했다

 

📌소스 코드

from collections import deque

n,m=map(int,input().split())
grid=[list(map(int,input().split())) for _ in range(n)]

dxs,dys=[-1,0,1,0],[0,1,0,-1]
def can_go(x,y):
    return 0<=x<n and 0<=y<m and grid[x][y]!=0

def bfs(startx,starty):
    q=deque([(startx,starty)])
    distance[startx][starty]=0
    while q:
        x,y=q.popleft()
        for dx,dy in zip(dxs,dys):
            nx,ny=x+dx,y+dy
            if can_go(nx,ny) and distance[nx][ny]==-1:
                distance[nx][ny]=distance[x][y]+1
                q.append((nx,ny))
    return distance

distance=[[-1]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if grid[i][j]==1 and distance[i][j]==-1:
            distance[i][j]=-1
        elif grid[i][j]==0:
            distance[i][j]=0
        elif grid[i][j]==2:
            endx,endy=i,j

result= bfs(endx,endy)
for row in result:
    print(*row)