728x90
문제 요약
지도에서 각 지점에 대해 목표 지점(값이 2인 지점)까지의 거리를 구하는 문제이다. 지도는 가로와 세로로만 움직일 수 있으며, 0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표 지점을 의미한다.
풀이 설명
이 문제는 너비 우선 탐색(BFS)를 사용하여 각 지점에서 목표 지점까지의 최단 거리를 구하는 문제이다.
BFS는 최단 거리를 구하는 데 적합한 알고리즘이다.
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
def bfs(graph, n, m):
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 # 목표 지점은 거리가 0
elif graph[i][j] == 0: # 갈 수 없는 땅은 거리 0
distance[i][j] = 0
while queue:
x, y = queue.popleft()
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m:
if graph[nx][ny] == 1 and distance[nx][ny] == -1:
distance[nx][ny] = distance[x][y] + 1
queue.append((nx, ny))
return distance
distances = bfs(graph, n, m)
for row in distances:
print(*row)
코드 설명
- 입력 처리:
sys.stdin.readline을 사용하여 빠르게 입력을 처리한다.- 지도 크기
n과m을 입력받고, 지도 정보를graph에 저장한다.
- BFS 초기화:
distance배열을 -1로 초기화한다. 이는 갈 수 있는 땅이지만 목표 지점에 도달할 수 없는 위치를 나타낸다.- 목표 지점(값이 2인 지점)을 큐에 추가하고, 그 지점의 거리를 0으로 설정한다.
- 갈 수 없는 땅(값이 0인 지점)은 거리 0으로 설정한다.
- BFS 탐색:
- 큐에서 지점을 꺼내, 그 지점의 상하좌우 인접 지점을 검사한다.
- 인접 지점이 갈 수 있는 땅(값이 1)이고, 아직 방문하지 않은 경우(거리가 -1), 거리를 현재 지점의 거리 + 1로 설정하고 큐에 추가한다.
- 결과 출력:
- BFS 탐색이 끝난 후, 각 지점의 거리 정보를 출력한다.
이 알고리즘은 지도 크기가 최대 1000x1000이므로 효율적으로 동작하며, 각 지점에서 목표 지점까지의 최단 거리를 구할 수 있다.
728x90
