BOJ 14940 - 쉬운 최단거리

문제

백준 온라인 저지 - 14940번

풀이 과정

목표지점에 도달하기 위한 최단거리를 구하는 문제입니다.
2차원 배열의 각 칸을 정점이라고 생각할 경우 모든 인접한 정점까지의 거리 값은 같기 때문에
BFS 를 이용해서 목표지점까지의 최단 거리를 구할 수 있습니다.

코드

import sys
from collections import deque


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


def find_start():
    for x in range(N):
        for y in range(M):
            if board[x][y] == 2:
                return [x, y]


def in_range(x, y):
    return 0 <= x < N and 0 <= y < M


def bfs(sx, sy):
    visit = [[-1] * M for _ in range(N)]
    q = deque()

    visit[sx][sy] = 0
    q.append([sx, sy])

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if in_range(nx, ny) and visit[nx][ny] == -1 and board[nx][ny]:
                visit[nx][ny] = visit[x][y] + 1
                q.append([nx, ny])

    for x in range(N):
        for y in range(M):
            if board[x][y] == 0:
                visit[x][y] = 0

    return visit


def solution():
    sx, sy = find_start()
    dist = bfs(sx, sy)

    for x in range(N):
        print(' '.join(map(str, dist[x])))


if __name__ == '__main__':
    N, M = list(map(int, sys.stdin.readline().split()))
    board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

    solution()