| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 19568 | 7788 | 6349 | 37.420% |
문제
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
입력
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.
출력
각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.
답안
from collections import deque
import math
import sys
# get input
height, width = map(int, sys.stdin.readline().split())
table = [list(map(int, sys.stdin.readline().split())) for _ in range(height)]
# find start point
start = [0, 0]
for i in range(height):
for j in range(width):
if table[i][j] == 2:
start = [i, j]
# initialize variables
distances = [[math.inf for _ in range(width)] for _ in range(height)]
distances[start[0]][start[1]] = 0
visited = [[False for _ in range(width)] for _ in range(height)]
visited[start[0]][start[1]] = True
for i in range(height):
for j in range(width):
if (table[i][j] == 0):
distances[i][j] = 0
visited[i][j] = True
queue = deque([(start[0], start[1])])
# bfs
while queue:
row, col = queue.popleft()
visited[row][col] = True
# adjacent cells are the cells that satisfies
# 1. their distance from the current cell is 1
# 2. they are within table
# 3. they are not visited
adjacents = list(filter(lambda x: not visited[x[0]][x[1]],
filter(lambda x: 0 <= x[0] < height and 0 <= x[1] < width,
[(row-1, col), (row, col-1), (row, col+1), (row+1, col)])))
for adjacent in adjacents:
row, col = adjacent[0], adjacent[1]
if not visited[row][col]:
queue.append((row, col))
visited[row][col] = True
if table[row][col] == 1:
# get distances from adjacent cells.
# if value of table[y][x] == 0, it means the cell is unreachable by any case
min_distance = min(list(map(lambda x: distances[x[0]][x[1]],
filter(lambda x: table[x[0]][x[1]] != 0,
filter(lambda x: 0 <= x[0] < height and 0 <= x[1] < width,
[(row-1, col), (row, col-1), (row, col+1), (row+1, col)])))))
distances[row][col] = min_distance + 1
# print answer. if not reachable, print -1
for line in distances:
print(' '.join(list(map(lambda x: str(x) if not math.isinf(x) else '-1', line))))풀이
BFS를 이용해 풀 수 있다.
목표 지점으로부터 다른 모든 접근 가능한 칸들로 완전탐색을 하면서, 탐색 depth가 하나 늘어날 때마다 그 거리를 기록하면 될 것이다.
1000 * 1000 크기의 테이블을 대상으로 탐색하므로 1초의 시간 안에 풀 수 있을 것 같다.
# find start point
start = [0, 0]
for i in range(height):
for j in range(width):
if table[i][j] == 2:
start = [i, j]먼저 시작점을 찾는다.
더 효율적으로 찾는 방법도 있겠지만, 어차피 해봤자 O(n)이라 일단 이렇게 구현했다.
# initialize variables
distances = [[math.inf for _ in range(width)] for _ in range(height)]
distances[start[0]][start[1]] = 0
visited = [[False for _ in range(width)] for _ in range(height)]
visited[start[0]][start[1]] = True
for i in range(height):
for j in range(width):
if (table[i][j] == 0):
distances[i][j] = 0
visited[i][j] = True
queue = deque([(start[0], start[1])])그 다음으로, 필요한 변수들을 초기화한다.
distances는 정답을 저장할 배열이다.
BFS를 위해 visited와 queue를 선언한 뒤, 적절히 초기화해준다.
# adjacent cells are the cells that satisfies
# 1. their distance from the current cell is 1
# 2. they are within table
# 3. they are not visited
adjacents = list(filter(lambda x: not visited[x[0]][x[1]],
filter(lambda x: 0 <= x[0] < height and 0 <= x[1] < width,
[(row-1, col), (row, col-1), (row, col+1), (row+1, col)])))BFS에서 인접 칸들을 찾는 부분이다.
주석에서 설명하고 있는 바와 같이,
- 상하좌우 거리가 1이며
- 범위를 벗어나지 않고
- 방문하지 않은
칸들을 adjacents에 저장한다.
# get distances from adjacent cells.
# if value of table[y][x] == 0, it means the cell is unreachable by any case
min_distance = min(list(map(lambda x: distances[x[0]][x[1]],
filter(lambda x: table[x[0]][x[1]] != 0,
filter(lambda x: 0 <= x[0] < height and 0 <= x[1] < width,
[(row-1, col), (row, col-1), (row, col+1), (row+1, col)])))))
distances[row][col] = min_distance + 1로직의 핵심 부분이다.
인접 칸들 중에서 가장 거리가 작은 값을 찾은 뒤, 그 거리에 +1을 하여 시작점으로부터 자기 자신까지의 거리를 구한다.
시작점으로부터의 거리를 이미 구한 다른 칸들은 그 거리가 최소임이 확실하므로, 그 거리에 +1을 한 값이 시작점으로부터 자기 자신까지의 최소 거리가 되는 것이다.
# print answer. if not reachable, print -1
for line in distances:
print(' '.join(list(map(lambda x: str(x) if not math.isinf(x) else '-1', line))))접근할 수 없는 칸들의 경우 -1을 출력해줘야 한다는 점에 유의해 정답을 출력한다. (이거 때문에 한 번 틀렸다…)
table[row][col]에 0이 저장되어 있는, 즉 접근할 수 없는 칸의 경우 if table[row][col] == 1:와 같이 distance 값을 바꿔주지 않았기 때문에 초기값 그대로 math.inf이다.
따라서 distances에 math.inf가 저장되어 있는 경우 -1을 출력하면 된다.
