💡 문제
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
.: 깨끗한 칸*: 더러운 칸x: 가구o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
💭 접근
이 문제를 처음 보았을 때 단순히 BFS를 통해 가장 먼저 도착하는 더러운 지점, 이곳에서 그 다음으로 가까운 더러운 지점까지의 거리를 더하는 방식으로 구현하였지만 실패하였다.
이유는 간단했는데, 아래의 경우를 보자.
. . .
. o *
* * *이 경우 오른쪽 x를 먼저 방문하는 경우 정답으로 4를, 아래쪽 x를 먼저 방문하는 경우 정답으로 5를 출력하는 것을 알 수 있었다. 따라서 BFS 방문 순서에 따라 정답이 달라질 수 있다는 것을 간과하였던 것이다.
따라서 다른 방법을 생각했는데, 먼저 로봇청소기의 시작지점을 0으로, 나머지 더러운 지점을 1 ~ n까지 번호를 메긴 후, 각 지점에서 다른 모든 지점까지의 거리를 구하여 마지막에 순열을 통해 더러운 지점을 방문할 순서를 정하는 것이다.
(더러운 지점의 개수가 10을 넘지 않기에 순열을 사용할 수 있을 것이라고 생각했다.)
예시와 코드를 보며 이해해보자. 입력으로 아래와 같이 주어졌다고 가정해보자.
. . . . .
. o . * .
. . . . .
. * . * .
. . . . .1. 입력으로 주어진 graph에 번호를 메기고 각 칸을 저장한다.
spots = []
num = 1
for i in range(h):
for j in range(w):
if graph[i][j] == 'o':
spots.append([i, j])
graph[i][j] = 0
if graph[i][j] == '*':
spots.append([i, j])
graph[i][j] = num
num += 1위 단계를 거치면 graph는 다음과 같이 변경된다.
. . . . .
. 0 . 1 .
. . . . .
. 2 . 3 .
. . . . .2. 각 지점에 대해 서로 간의 거리를 구한다. (BFS)
spot_dist = [[float('inf') for _ in range(num)] for _ in range(num)]
for spot in spots:
x, y = spot
start_num = graph[x][y]
spot_dist[start_num][start_num] = 0
bfs(x, y, start_num)# BFS 함수
def bfs(x, y, start_num):
q = deque()
q.append([x, y, 0])
visited = [[0 for _ in range(w)] for _ in range(h)]
visited[x][y] = 1
while q:
x, y, cnt = q.popleft()
if type(graph[x][y]) == int:
spot_dist[start_num][graph[x][y]] = cnt
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] != 'x' and visited[nx][ny] == 0:
visited[nx][ny] = 1
q.append([nx, ny, cnt + 1])
위 단계를 거치면 spot_dist는 다음과 같이 저장된다.
[0, 2, 2, 4]
[2, 0, 4, 2]
[2, 4, 0, 2]
[4, 2, 2, 0]spot_dist[1][2]는 1번 지점에서 2번지점까지의 거리를 의미한다.
3. 순열을 구하여 더러운 지점을 방문할 순서를 정하고, 정답을 갱신한다. (DFS)
def dfs(curr, cnt, depth):
global ans
if depth == num - 1:
ans = min(ans, cnt)
return
for next in range(num):
if visited[next] == 0:
visited[next] = 1
dfs(next, cnt + spot_dist[curr][next], depth + 1)
visited[next] = 0이렇게 되면 ans에 모든 더러운 지점을 방문하기 위한 최소 이동 횟수를 구할 수 있으며, 만약 방문 불가능한 칸이 있다면 spot_dist에는 inf 값이 저장되기 때문에 모든 과정을 거친 후에도 ans에 inf값이 저장되어 있다면 -1을 출력한다.
📒 코드
import sys
input = sys.stdin.readline
from collections import deque
def bfs(x, y, start_num):
q = deque()
q.append([x, y, 0])
visited = [[0 for _ in range(w)] for _ in range(h)]
visited[x][y] = 1
while q:
x, y, cnt = q.popleft()
if type(graph[x][y]) == int:
spot_dist[start_num][graph[x][y]] = cnt
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] != 'x' and visited[nx][ny] == 0:
visited[nx][ny] = 1
q.append([nx, ny, cnt + 1])
def dfs(curr, cnt, depth):
global ans
if depth == num - 1:
ans = min(ans, cnt)
return
for next in range(num):
if visited[next] == 0:
visited[next] = 1
dfs(next, cnt + spot_dist[curr][next], depth + 1)
visited[next] = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while True:
w, h = map(int, input().split())
if w == 0 and h == 0: break
graph = [list(input()) for _ in range(h)]
spots = []
num = 1
for i in range(h):
for j in range(w):
if graph[i][j] == 'o':
spots.append([i, j])
graph[i][j] = 0
if graph[i][j] == '*':
spots.append([i, j])
graph[i][j] = num
num += 1
spot_dist = [[float('inf') for _ in range(num)] for _ in range(num)]
for spot in spots:
x, y = spot
start_num = graph[x][y]
spot_dist[start_num][start_num] = 0
bfs(x, y, start_num)
ans = float('inf')
visited = [0 for _ in range(num)]
visited[0] = 1
dfs(0, 0, 0)
if ans == float('inf'):
print(-1)
else:
print(ans)💭 후기
BFS를 사용하여 각 지점 간의 최단거리를 구하고, DFS르 사용하여 각 지점을 방문할 순서를 정하여 정답을 구하는 문제로, 코드 구현은 어렵지 않았지만 아이디어를 떠올리기 까다로운 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/4991
