[백준 - 14940] 쉬운 최단거리 🐢

❓ Problem

바로가기

🤔 How

목표지점(주어진 문자상 2인지점) 부터 이동 가능한 거리라면 거리 아닐경우 -1 로 표시한다. 원래 이동하지못하는경우라면 0을 표시하여 출력한다.

조건

1. 원래 이동할수 없는 지역일경우 0으로 표시해야한다.

2. 이동가능한 지역이지만 목표지점까지 도달하지못할경우 -1로 표시해야한다.

3. 그외 모든 이동가능한 좌표에대해서 목표지점부터까지의 거리를 표시한다 (맨해튼 거리)

❗ Solve

# 쉬운 최단거리
import sys
from collections import deque
input =sys.stdin.readline
moves=[(0,1),(0,-1),(1,0),(-1,0)]
def find_target(board): # 좌표가 2인목표지점을 찾는함수
    for y in range(len(board)):
        for x in range(len(board[0])):
            if board[y][x]==2:
                return (y,x)

def draw_board(n): # 보드 그리기
    board=[]
    for y in range(n):
        board.append(list(map(int,input().split())))
    return board

def bfs(board,ty,tx):
    # -1 로 모든좌표 초기화
    bfs_board=[[-1]*len(board[0]) for _ in range(len(board))]

    visited=[[False]*len(board[0]) for _ in range(len(board))]

    q=deque()
    visited[ty][tx]=True
    # 목표지점 의 경우 자신이므로 거리 0
    bfs_board[ty][tx]=0

    q.append((ty,tx))
    while q:
        cy,cx=q.popleft()

        for move in moves:
            dy,dx=move
            ny,nx=dy+cy,dx+cx
            if 0<=ny<len(board) and 0<=nx<len(board[0]) and board[ny][nx]!=0 and not visited[ny][nx]:
                visited[ny][nx]=True
                bfs_board[ny][nx]=bfs_board[cy][cx]+1
                q.append((ny,nx))

    for y in range(len(bfs_board)):
        for x in range(len(bfs_board[0])):
            if board[y][x]==0: # 원래 갈수없는지역일경우 0으로 변경한다.
                bfs_board[y][x]=0

    # 출력
    for y in range(len(bfs_board)):
        print(*bfs_board[y])      




def solution():
    n,m=map(int,input().split())
    board = draw_board(n)
    ty,tx=find_target(board)
    bfs(board,ty,tx)
    pass
if __name__=="__main__": # 실행되는 부분
    solution()
    pass