14940. 쉬운 최단거리 (Python)

14940번: 쉬운 최단거리

 

풀이

 목표지점(2)의 위치를 구해서 해당 위치에서부터 bfs로 탐색을 하면 된다. 정답을 담아주는 배열의 초기 값에는 지도의 값이 1인 좌표에는 -1을 넣어주고 0인 좌표에는 0을 넣어준다. bfs 탐색을 하며 해당 좌표에 도착하는 거리를 정답 배열에 넣어주면 된다.

 

코드

from collections import deque

# 범위 탐색을 위한 함수 
def isRange(x, y):
    return 0 <= x < n and 0 <= y < m


if __name__ == '__main__':
    n, m = map(int, input().split()) # n: 세로 길이, m: 가로 길이

    board = []
    answer = [[-1 for _ in range(m)] for _ in range(n)] # 목표지점에서 해당 좌표까지의 거리를 담아두는 정답 배열
    visited = [[False for _ in range(m)] for _ in range(n)] # 방문 여부 체크 배열
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for i in range(n):
        line = list(map(int, input().split()))
        board.append(line)

        for j in range(m):
            if line[j] == 0: # 0인 땅에 해당하는 좌표는 거리를 0으로 초기화해준다.
                answer[i][j] = 0
            elif line[j] == 2: # 시작 좌표 
                sx, sy = i, j

    q = deque()
    q.append((sx, sy, 0))
    visited[sx][sy] = True
    answer[sx][sy] = 0

    # bfs를 통해 탐색하면서 해당 좌표까지의 거리를 넣어준다.
    while q:
        x, y, dis = q.popleft()

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if not isRange(nx, ny) or visited[nx][ny] or board[nx][ny] == 0:
                continue

            answer[nx][ny] = dis + 1
            visited[nx][ny] = True
            q.append((nx, ny, dis+1))

    for i in range(n):
        for j in range(m):
            print(answer[i][j], end=' ')
        print()