Problem
문제
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
.: 깨끗한 칸
*: 더러운 칸
x: 가구
o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
Solution
먼저 각 더러운 칸 사이의 최소 길이를 구한다. 그 다음 어떤 순서로 더러운 칸을 청소해야 최소 거리로 모든 칸을 청소할 수 있는지 계산한다.
더러운 칸 사이의 최소 길이는 BFS를 이용해 구한다. 다음으로 백트래킹으로 더러운 칸의 모든 순서를 탐색하면서 최소 거리를 구할 수 있다.
Python Code
from sys import stdin
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
INF = float('inf')
def fint_distance_to_target(start_pos, target_pos):
global w, h, board
q = deque()
visited = [[False for _ in range(w)] for _ in range(h)]
x, y = start_pos
q.append([x, y, 0])
visited[x][y] = True
while q:
x, y, cnt = q.popleft()
if x == target_pos[0] and y == target_pos[1]:
return cnt
for t in range(4):
nx = x + dx[t]
ny = y + dy[t]
if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != 'x' and not visited[nx][ny]:
q.append([nx, ny, cnt + 1])
visited[nx][ny] = True
return INF
def make_combination(depth, target_cnt, start_pos, now_dist):
global result, check, targets
if now_dist >= result:
return
if depth == target_cnt:
if now_dist < result:
result = now_dist
return
for i in range(target_cnt):
if not check[i]:
next_dist = now_dist + dist[start_pos][i]
check[i] = True
make_combination(depth + 1, target_cnt, i, next_dist)
check[i] = False
while True:
w, h = map(int, stdin.readline().split())
if w == 0 and h == 0:
break
board = [stdin.readline().rstrip() for _ in range(h)]
targets = []
start_pos = []
for i in range(h):
for j in range(w):
if board[i][j] == '*':
targets.append([i, j])
elif board[i][j] == 'o':
start_pos = [i, j]
dist = [[INF for _ in range(len(targets) + 1)] for _ in range(len(targets) + 1)]
for i in range(len(targets)):
for j in range(len(targets)):
cnt = fint_distance_to_target(targets[i], targets[j])
dist[i][j] = cnt
for i in range(len(targets)):
cnt = fint_distance_to_target(start_pos, targets[i])
dist[len(targets)][i] = cnt
dist[i][len(targets)] = cnt
dist[len(targets)][len(targets)] = 0
check = [False for _ in range(len(targets))]
result = INF
make_combination(0, len(targets), len(targets), 0)
if result != INF:
print(result)
else:
print(-1)
