문제 링크
https://www.acmicpc.net/problem/4991
🕒 Python 풀이시간: 60분
from collections import deque
dx=[0,0,-1,1]
dy=[-1,1,0,0]
def bfs(distTree,key,start,dust,board):
x,y=start
q=deque([(x,y)])
visited=[[-1]*w for _ in range(h)]
visited[x][y]=0
while q:
now=q.popleft()
for i in range(4):
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=h or ny>=w:
continue
if board[nx][ny]=='x':
continue
if visited[nx][ny]!=-1:
continue
q.append((nx,ny))
visited[nx][ny]=visited[now[0]][now[1]]+1
if key=='cleaner':
distTree['cleaner']=dict()
for dustKey in dust:
distTree['cleaner'][dustKey]=visited[dust[dustKey][0]][dust[dustKey][1]]
else:
distTree[key]=dict()
for dustKey in dust:
if key!=dustKey:
distTree[key][dustKey]=visited[dust[dustKey][0]][dust[dustKey][1]]
def updateDistTree(distTree,cleaner,dust,board):
for k in dust.keys():
bfs(distTree,k,dust[k],dust,board)
bfs(distTree,'cleaner',cleaner,dust,board)
def dfs(fromDust,dust,deep,visited,distSum):
global answer,distTree
if deep==dustNum:
answer=min(answer,distSum)
return
for i in dust.keys():
if visited&(1<<i):
continue
dfs(i,dust,deep+1,visited|(1<<i),distSum+distTree[fromDust][i])
while True:
w,h=map(int,input().split())
if w==0 and h==0:
break
board=[]
cleaner=tuple()
dust=dict()
dustNum=0
for i in range(h):
arr=list(input())
for j in range(w):
if arr[j]=='.' or arr[j]=='x':
continue
if arr[j]=='o':
cleaner=(i,j)
elif arr[j]=='*':
dust[dustNum]=(i,j)
dustNum+=1
board.append(arr)
distTree=dict()
updateDistTree(distTree,cleaner,dust,board)
canFoundAll=True
for k in distTree['cleaner'].keys():
if distTree['cleaner'][k]==-1:
canFoundAll=False
break
if not canFoundAll:
print(-1)
continue
answer=1e9
visited=0
for dk in distTree['cleaner'].keys():
dfs(dk,dust,1,visited|(1<<dk),distTree['cleaner'][dk])
print(answer)로봇 청소기 시뮬레이션 문제! 🤖🧹
로봇 청소기를 다루는 시뮬레이션 문제이다. 비트마스킹을 연습하려고 뽑은 문제였는데... 단순 순열 짤때 아니면 비트마스킹을 쓴 적이 없다.
먼지와 벽, 그리고 청소기가 2차원 배열로 주워지고 해당 먼지를 청소하는 최단 거리를 구하는 문제이다. 이 때, 모든 먼지를 청소하지 못하면 -1을 return 한다. 그렇기 때문에 단순히 bfs로 모든 먼지를 찾아서 청소기와 먼지들 사이간의 거리를 구해놓고 그 후에 DFS로 모든 경로를 가지치기하면서 탐색하면 되지 않을까라는 생각이 들었다. 순열처럼 순서처리를 해야하기 때문에 이 때, 비트마스킹을 쓰는 건가보다 했다.
시간복잡도를 먼저 계산해봐도 전체크기가 400이고 먼지 수가 많아야 10개 이기 때문에 대량 연산량이 4,000이고 모든 순열을 구하는 방법을 따져봐도 그렇게 많지 않았기에 진행하였다.
먼저 dict으로 먼지와 청소기의 좌표를 받아두고 BFS를 수행한다. 2차원 배열을 써서 거리를 기록해도 됬지만 어찌하다보니 이중 dict을 써서 풀었다. 거리를 일일이 전부 기록하고 나서 이 기록에 대해서 하나를 기준으로 잡고, 나의 경우는 청소기를 기준으로 잡았다. 이 기준으로 모든 거리가 0이상으로 갱신되었는지 보는거다. 만약 -1이 있다면 벽 때문에 가지 못하는 경우이기 때문에 -1을 출력 후 다음 케이스로 넘어간다.
그 이후에는 visited를 비트로 둔 후에 순열을 수행한다. 거리를 구한 것을 가지고 진행하여 합산하면서 들어가서 최종 답을 갱신시켜 주면 된다.
이렇게 Python로 백준의 "로봇 청소기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
