[문제 바로가기] https://www.acmicpc.net/problem/4991
📌문제 설명
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다.각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
- .: 깨끗한 칸
- *: 더러운 칸
- x: 가구
- o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
💡 문제 풀이
BFS + 순열로 해결한 문제다.
처음엔 단순히 로봇 청소기의 위치에서 가까운 더러운 칸을 깨끗한 칸으로 바꾸는 방식으로 진행하였다.(= 그리디 알고리즘)
하지만, 그리디로 접근할 경우 같은 거리의 더러운 칸이 여러개 존재할 경우 어떤 칸을 먼저 청소하느냐에 따라서 결과가 달라진다.
→ 따라서, 그리디가 아닌 '완전 탐색' 방법으로 접근해야했다.
※ 문제 해결 순서
-
로봇 청소기, 더러운 칸의 위치를 구한다. 더러운 칸의 좌표는 dusts 배열에 담는다.
-
첫 번째로 청소하게 될 더러운 칸까지의 거리는 '로봇 청소기'위치에서 해당 칸까지의 거리이다. '로봇 청소기 ~ (모든)더러운 칸'의 거리를 구한다. → BFS를 이용하여 '더러운 칸'까지의 거리를 cleaner 배열에 담는다.
-
2번에서 만약 '로봇 청소기'가 '가구(x)'의 배치로 인하여 방문할 수 없는 칸이 나타나면(visited 값이 0이면) '-1'을 출력하고 진행을 멈춘다.
-
로봇 청소기가 처음 청소할 칸을 정하게 되면 남은 모든 더러운 칸들을 청소하는데 소요되는 거리는 각 칸의 거리의 총합이다.
따라서, 모든 더러운 칸 사이의 거리를 우선 구한다. → dists -
모두 깨끗한 칸으로 바꾸는 이동횟수는 청소하려는 칸의 '순서'에 따라 달라진다. 즉, 순열을 이용하여 청소하려는 칸의 순서를 정하고 4번에서 구한 거리를 이용하여 정답을 도출한다.
코드는 다음과 같다.
import sys
from collections import deque
from itertools import permutations
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def bfs(i, j):
visited = [[0] * w for _ in range(h)]
visited[i][j] = 1
queue = deque([(i, j)])
while queue:
r, c = queue.popleft()
for idx in range(4):
nr = r + d[idx][0]
nc = c + d[idx][1]
if 0 <= nr < h and 0 <= nc < w and not visited[nr][nc]:
if maps[nr][nc] != 'x':
queue.append((nr, nc))
visited[nr][nc] = visited[r][c] + 1
return visited
while True:
w, h = map(int, input().split())
if w + h:
maps = [list(''.join(map(str, sys.stdin.readline().rstrip()))) for _ in range(h)]
dusts = [] # 더러운 칸의 좌표를 담을 배열
cr, cc = 0, 0 # 로봇 청소기의 위치(행, 열)
for r in range(h):
for c in range(w):
if maps[r][c] == 'o':
cr, cc = r, c
elif maps[r][c] == '*':
dusts.append((r, c))
cleaner = [0] * len(dusts) # 로봇 청소기 ~ 첫 번째로 청소할 더러운 칸까지의 거리를 담을 배열
visited = bfs(cr, cc)
is_possible = True # 로봇 청소기가 모든 더러운 칸을 방문할 수 있는지 확인
for idx, rc in enumerate(dusts):
temp = visited[rc[0]][rc[1]]
if not temp: # 로봇 청소기가 방문할 수 없는 칸이 나오면 False
print(-1)
is_possible = False
break
cleaner[idx] += temp - 1
if is_possible:
dists = [[0] * (len(dusts)) for _ in range(len(dusts))] # 더러운 칸마다의 거리를 계산한다.
for i in range(len(dusts) - 1):
visited = bfs(dusts[i][0], dusts[i][1])
for j in range(i + 1, len(dusts)):
dists[i][j] = visited[dusts[j][0]][dusts[j][1]] - 1
dists[j][i] = dists[i][j]
answer = int(1e9)
for li in permutations(range(len(dists))): # 순열을 이용하여 최적의 순서를 찾는다.
temp = cleaner[li[0]]
start = li[0]
for idx in range(1, len(li)): # 순열을 기준으로 시작점(start), 도착점(end)을 바꿔가며 거리를 더한다.
end = li[idx]
temp += dists[start][end]
start = end
answer = min(answer, temp) # answer에 이동횟수의 최소값을 담는다.
print(answer)
else:
break ※ Python3에서는 '시간초과'가 발생한다.
