[BOJ 14940] 쉬운 최단 거리

Breadth-First Search

[BOJ 14940] 쉬운 최단 거리

문제

구조화

• n은 세로(y), m은 가로(x)
• 탐색할 지도 좌표 생성
• 좌표에서 값이 0일 경우 갈 수 없음, 1일 경우 갈 수 있고, 2일 경우는 목표지점
• 갈 수 있는 좌표 중 각 좌표에서 목표지점까지의 거리를 구하는 문제
• 좌표의 값이 2인 지점이 start point
• 이를 위해 지도의 좌표를 입력받은 후 값이 2인 좌표를 큐에 추가
• 순회 시 인덱싱은 [y][x] 형태
• BFS로 탐색하되, 이동은 4방향으로 가능
• 초기 좌표가 2인 지점을 기준으로 BFS 탐색
• 현재 좌표에서 이동 가능 공간(좌표를 벗어나지 않고)임과 동시에, 좌표의 값이 0이 아닌 좌표일 경우 이전 좌표의 값에 +1씩 하며 탐색
• 시작 값이 2이므로, 탐색 후 각 좌표 값에서 2를 뺴주되, 0인 경우 이동할 수 없는 좌표이므로 Continue

해답

# 1은 갈 수 있는 땅, 0은 갈 수 없는 땅, 2는 목표 지점
# n은 세로 크기, m은 가로 크기
from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int, input().split())#n은 y m은 x
mapper = []
for i in range(n):
    mapper.append(list(map(int, input().split())))
dx=(0,0,-1,1)
dy=(1,-1,0,0)
a=deque()
for y in range(n):
    for x in range(m):
        if mapper[y][x]==2:
            a.append([y,x])
def bfs():
    while len(a):
        y,x = a.popleft()
        for i in range(4):
            new_x = x+dx[i]
            new_y = y+dy[i]
            if new_x>=m or new_y >=n or new_x<=-1 or new_y <= -1:
                continue
            else:
                if mapper[new_y][new_x]==1:
                    mapper[new_y][new_x] = mapper[y][x]+1
                    a.append([new_y,new_x])
bfs()
for i in range(len(mapper)):
    for j in range(len(mapper[i])):
        if mapper[i][j]==0:
            continue
        else:
            mapper[i][j]= mapper[i][j]-2
for c in mapper:
    print(*c)