[백준/파이썬] 14940번: 쉬운 최단거리

문제

https://www.acmicpc.net/problem/14940

풀이

• 모든 지점에 대해서 목표지점까지의 거리
• 가로와 세로로만 움직일 수 있다

목표지점까지의 거리를 찾는 문제이기 때문에 BFS로 풀어야 합니다.

우선 지도를 입력받을 때 2의 위치를 파악하기 위해 지도를 입력받을 때 검사를 진행했습니다.

for i in range(n):
	row = list(map(int,input().split()))
    graph.append(row)
    for j in range(m):
    	if row[j] == 2:
        	x,y = i,j

(row에서 2를 찾을 때 row[i][j]라고 했다가 계속 오류가 발생해서 찾느라 고생 좀 했읍니다..)

입력 받은 graph를 통해 결과를 저장할 visited 배열을 선언했습니다.
저는 graph를 모두 검사하여 이동할 수 있는 곳(1)이면 -1로 설정하고 지나가지 못하는 곳(0)이면 0으로 설정했습니다.

visited = [[-1 if graph[i][j] == 1 else 0 for j in range(m)] for i in range(n)]

이제 목표지점으로부터의 거리를 측정할 함수를 선언해줍니다.

def bfs(X,Y):
    
    # 상,하,좌,우 방향
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    queue = deque([(X,Y)]) # 시작 지점
    visited[X][Y] = 0 # 시작 지점으로부터 거리는 0

    while queue:
        x,y = queue.popleft()
        
        # 4방향 탐색
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < m: # 범위 내일 때
                if visited[nx][ny] == -1 and graph[nx][ny] == 1: # 방문하지 않은 곳 && 이동할 수 있는 땅
                    queue.append((nx,ny))
                    visited[nx][ny] = visited[x][y] + 1 # 거리 +1

코드

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

def bfs(X,Y):
    queue = deque([(X,Y)])
    visited[X][Y] = 0

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if visited[nx][ny] == -1 and graph[nx][ny] == 1:
                    queue.append((nx,ny))
                    visited[nx][ny] = visited[x][y] + 1

if __name__ == "__main__":
    n,m = map(int,input().split())

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

    graph = []
    x,y = 0,0

    for i in range(n):
        row = list(map(int,input().split()))
        graph.append(row)
        for j in range(m):
            if row[j] == 2:
                x,y = i,j

    visited = [[-1 if graph[i][j] == 1 else 0 for j in range(m)] for i in range(n)]

    bfs(x,y)
    for row in visited:
        print(*row)