[백준] 14940번 쉬운 최단거리 해설 및 풀이 (Python)

백준 14940번 쉬운 최단거리

https://www.acmicpc.net/problem/14940

 

 

---

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

 

---

 

문제 유형

그래프 이론

그래프 탐색

너비 우선 탐색

 

풀이 방법 도출

 

1. 주어진 지도에서 목표 지점(2)의 좌표를 찾습니다. 이를 BFS의 시작점으로 큐에 추가합니다.
2. BFS는 시작 지점에서부터 인접한 위치를 차례로 탐색하며 거리 값을 증가시킵니다.
3. 모든 위치의 거리를 -1로 초기화하여 아직 방문하지 않았음을 표시합니다.
4. 갈 수 없는 땅은 0으로 설정하여 BFS에서 탐색되지 않도록 합니다.
5. 큐에서 위치를 하나씩 꺼내면서 상, 하, 좌, 우로 이동 가능한 모든 지점을 탐색합니다.
6. 아직 방문하지 않은 곳은 현재 위치에서 +1을 한 값을 저장하고, 큐에 추가하여 탐색을 계속 진행합니다.
7. BFS 종료 후에도 -1인 위치는 목표 지점에 도달할 수 없는 곳이므로 그대로 유지합니다.

 

시간 복잡도

• O(N * M)

---

 

핵심 코드 삽입 및 설명

import sys
from collections import deque


def bfs(n, m, graph):
    # 거리 저장을 위한 배열
    distance = [[-1] * m for _ in range(n)]
    
    # 목표지점의 위치 찾기 및 초기화
    queue = deque()
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 2:
                queue.append((i, j))
                distance[i][j] = 0  # 목표지점의 거리
                graph[i][j] = 1  # 방문 가능하도록 변경
            elif graph[i][j] == 0:
                distance[i][j] = 0  # 갈 수 없는 땅은 0으로 유지
    
    # 상, 하, 좌, 우 이동을 위한 방향 벡터
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # BFS 실행
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            # 범위 밖이면 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            
            # 갈 수 없는 땅이면 거리 유지
            if graph[nx][ny] == 0:
                continue
            
            # 아직 방문하지 않은 갈 수 있는 땅인 경우
            if distance[nx][ny] == -1:
                distance[nx][ny] = distance[x][y] + 1
                queue.append((nx, ny))
    
    return distance


# 입력 받기
n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


# BFS 실행 후 거리 배열 반환
result = bfs(n, m, graph)


# 결과 출력
for row in result:
    print(*row)