[BOJ] 14940. 쉬운 최단거리 (🥈, BFS/DFS)

문제

출력 조건

원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

풀이

문제는 어렵지 않았는데 출력 조건을 제대로 안 봐서 세 번 틀렸다

원래 갈 수 있는 부분에서 도달할 수 없는 위치는 -1

도달할 수 없는 위치는 탐색 중에 만날 일이 없기 때문에 애초에 값을 -1로 초기화해둬야 한다. visited 배열에 최단 거리의 값을 입력할 것이므로 배열의 모든 값을 -1로 초기화한다

원래 갈 수 없는 땅의 위치는 0을 출력해라
목표지점 2는 한 개 뿐이다

visited 배열을 통해 최단거리 값을 저장할 거기 때문에 arr[i][j] == 0인 값들에 대해서 visited 배열의 값을 0으로 바꿔준다. 어차피 초반에 목표지점 2의 위치를 찾아야 하기 때문에 _init()이라는 초기화 함수에서 한 번에 실행해준다

최종 코드

# 424ms

# 2의 위치를 찾고 & 갈 수 없는 곳의 visited 값을 0으로 초기화
def _init():
    si = sj = -1
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 2:
                si, sj = i, j
            elif not arr[i][j]:
                visited[i][j] = 0
    return si, sj

# bfs 탐색으로 각 칸에 대해 2에서부터의 최단 거리 구하기
def bfs(si, sj):
    queue = [(si, sj)]
    
    visited[si][sj] = 0
    while queue:
        i, j = queue.pop(0)

        for k in range(4):
            ni = i + di[k]
            nj = j + dj[k]
            if ni<0 or nj<0 or ni>=n or nj>=m or visited[ni][nj] != -1:
                continue
                
            visited[ni][nj] = visited[i][j] + 1
            queue.append((ni, nj))


n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[-1] * m for _ in range(n)]

si, sj = _init()
di = (0, 1, -1, 0)
dj = (1, 0, 0, -1)

bfs(si, sj)

for row in visited:
    print(*row)