문제
[문제]
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다.
이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다.
칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며,
로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다.
로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다.
또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한
이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
[입력]
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20)
둘째 줄부터 h개의 줄에는 방의 정보가 주어진다.
방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
.: 깨끗한 칸
*: 더러운 칸
x: 가구
o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.아이디어
더러운 칸을 어떤 순서로 방문해야 최소 이동 횟수로 모든 더러운 칸을 방문할 수 있는가?
(pypy3 통과, Python3 시간초과)
-
출발점 및 더러운 칸의 좌표를
points리스트에 저장한다.
(이때, 항상 로봇 청소기의 최초 위치인 시작점은points[0]에 저장한다.) -
2차원 리스트
min_dist를 생성한다.min_dist[i][j]는points[i]에서points[j]까지의 최단거리이다.-
points[i]에서 모든 칸까지의 최단거리를 BFS로 구한 뒤, 결과를dist에 저장한다.- 이때, 도달할 수 없는 칸이 있다면
-1을 출력한다.
- 이때, 도달할 수 없는 칸이 있다면
-
points[i]에서points[j]까지의 최단 거리는dist[points[j][0]][points[j][1]] -
이와 같이 정리할 수 있다.
min_dist[i][j] = min_dist[j][i] = dist[points[j][0]][points[j][1]]
-
-
이후, 더러운 칸의 방문 순서를 정하고(순열),
각 순서로 이동할 때 최소 이동 횟수가 몇인지 구하여 이를 출력한다.- 더러운 칸의 개수는 10개를 넘지 않는다는 조건이 있으므로 시간초과 발생하지 않는다.
- 최소 이동 횟수는 위에서 구해놓은
min_dist를 이용하여 쉽게 구할 수 있다.
풀이
- 코드 (pypy3 통과, Python3 시간초과)
import sys
input = sys.stdin.readline
from collections import deque
from itertools import permutations
dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]
"""
(r, c)에서 모든 지점에 대해 BFS를 하여 최단거리를 구한 뒤
모든 지점에 대한 최단거리를 저장한 dist를 return
"""
def bfs(arr, r, c):
n = len(arr)
m = len(arr[0])
q = deque([(r, c)])
dist = [[-1] * m for _ in range(n)]
dist[r][c] = 0
while q:
r, c = q.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < n and 0 <= nc < m:
if arr[nr][nc] == 'x':
continue
if dist[nr][nc] > -1:
continue
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
return dist
"""
dist를 통해 방문할 수 없는 지점이 있는지 확인한다.
"""
def exists_non_reachable_point(arr, dist):
n = len(arr)
m = len(arr[0])
for r in range(n):
for c in range(m):
if arr[r][c] == 'x':
continue
if dist[r][c] == -1:
return True
return False
"""
main
"""
while True:
m, n = map(int, input().split())
if m == 0 and n == 0:
break
arr = [list(input().strip()) for _ in range(n)]
# 로봇 청소기의 시작 위치를 찾는다
start_r = -1
start_c = -1
for r in range(n):
for c in range(m):
if arr[r][c] == 'o':
start_r = r
start_c = c
break
# 탐색해야 할 지점: 출발점 + 더러운 칸
points = [(start_r, start_c)]
for r in range(n):
for c in range(m):
if arr[r][c] == '*':
points.append((r, c))
# min_dist[i][j] = points[i] - points[j]의 최단거리
INF = float('inf')
min_dist = [[INF] * len(points) for _ in range(len(points))]
# 최단거리를 저장할 변수
answer = INF
"""
point[i] ~ points[j] 최단 거리를 min_dist에 저장한다.
"""
for i in range(len(points)-1):
# dist: points[i]에서 전 지점으로의 최단거리를 구한 결과
i_row, i_col = points[i]
dist = bfs(arr, i_row, i_col)
# 방문할 수 없는 지점이 있는 경우 -1
if exists_non_reachable_point(arr, dist):
answer = -1
break
for j in range(i+1, len(points)):
if i == j:
min_dist[i][j] = 0
j_row, j_col = points[j]
min_dist[i][j] = min_dist[j][i] = dist[j_row][j_col]
"""
테스트 출력용
print("===== min_dist =====")
for row in min_dist:
print(row)
"""
if answer == -1:
print(answer)
else:
"""
points[0](시작점)을 제외하고 나머지 지점들로 순열을 만든다.
이후, 각각의 케이스에서 모든 칸을 청소할 때까지 걸리는 거리를 구하고, 그 중 최소를 구한다.
"""
orders = list(permutations(range(1, len(points)), len(points) - 1))
for order in orders:
tmp_dist = 0
for i in range(len(order)):
if i == 0:
# 시작점에서 order[i]번째 더러운 칸까지의 거리를 구한다.
tmp_dist += min_dist[0][order[i]]
else:
# order[i-1]번째 더러운 칸에서 order[i]번째 더러운 칸까지의 거리를 구한다.
tmp_dist += min_dist[order[i-1]][order[i]]
if answer > tmp_dist:
answer = tmp_dist
print(answer)참고 사이트
코뉴로그