[백준/4991/파이썬] 로봇 청소기

https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

Problem

• 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
• 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
• 방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

조건

• 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
• 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

입력은 여러 개의 테스트케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

• .: 깨끗한 칸
• *: 더러운 칸
• x: 가구
• o: 로봇 청소기의 시작 위치

더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

SOL

처음에는 BFS를 돌아주되, "*" (먼지)를 만나면, visited 방문을 초기화 하는 방법으로 구현을 하였다. 하지만, 그렇게 된다면 먼지를 만날 때마다, 20*20의 board를 전부 탐사해주는 불상사가 일어난다. 20*20 ^10 이므로, 이건 무적권 TL이 발생한다.

 

즉 ,BFS를 돌아주되, 내가 들렸다온 , 내가 뭔가 누구는 만났다는 상태를 저장하기위해서 제일 좋은 방법은, 몇일전에 풀었던, 아 맞다! 우산! 에서와 같이 , BFS + TPS(비트마스킹) 방법이 있고, 조금 더 사람에게 직관적인 방법은 BFS+ 순열을 이용한 완전탐색이 있다. 저번에는 비트마스킹으로 풀어봤으니까, BFS+완전탐색으로 풀어보자!

 

BFS+ 완전탐색

먼지들을 어떠한 순서로 거치게되는지 하나하나 다 비교해주는 완전탐색 알고리즘이다.

7 5
.......
.o...*.
.......
.*...*.
.......

예를들어, 위와같은 input이 있다고 하자.

 

우리는 방의 정보가 주어졌을 때, 최소한의 움직임으로 먼지들을 다 방문해야한다. 그러기 위해서 필요한 정보가 무엇이 있을까?

• 로봇청소기에서 각 먼지 사이의 거리
• 각 먼지들과 먼지 사이의 거리 

이 두가지 정보가 있다면, 로봇 청소기에서 출발해서,모든 경우의 수를 보면 어느 경로를 택해서 가는게 가장 빠른지 고를 수 있다. 위의 input을 그래프의 관계로 나타내면 더 직관적으로 이해하기 쉬워진다.

R(로봇청소기)에서, 각각의 먼지(편의상 1~3번 먼지라고 해줌)까지의 거리를 나타내주었다.

이렇게 되면, R-> 1->2->3 이 빠른지, R ->3->1->2가 거리가 작은지 등등을 비교할 수 있게 된다.

즉, (1,2,3)의 모든 순서를 고려하면, 최소의 거리를 구할 수 있게 된다. 

TL checking

먼지의갯수가 최대 10개이므로, 10!이므로 300만정도된다. 그리고, 각각의 거리를 구하는건 20*20 이고, 이 둘은 곱의 관계가 아니라, 합의 관계이다. 그러므로, 충분히 가능하다.

import sys
from collections import deque
from itertools import permutations 
input= sys.stdin.readline
dx=[0,1,0,-1]
dy=[1,0,-1,0]

#시작점에서 거리를 기록해준 배열을 반환.
def bfs(y,x):
    dq=deque()
    dq.append((y,x))
    visited=[[0 for _ in range(M)] for _ in range(N)]
    visited[y][x]=1
    while dq:
        y,x=dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if not(0<=ny<N and 0<=nx<M):
                continue
            if board[ny][nx] !="x" and not visited[ny][nx]:
                visited[ny][nx]=visited[y][x] +1
                dq.append((ny,nx))
    return visited

while True:
    M,N=map(int,input().split())
    if M==0 and N==0:
        break
    board=[]
    dusts=[]
    for i in range(N):
        tmp=list(input().rstrip())
        board.append(tmp)
        for j in range(M):
            if tmp[j]=="o":
                sy,sx=i,j
            elif tmp[j]=="*":
                dusts.append((i,j))
    #print(dusts)
    #print(board)
    #청소기에서, 먼지까지 거리를 담은 배열
    cleaner=[0]*len(dusts)
    visit=bfs(sy,sx)
    flag=True
    #청소기에서 0~N-1 먼지까지의 거리를 저장.
    for idx,value in enumerate(dusts):
        tmp=visit[value[0]][value[1]]
        #tmp ==0
        if not tmp:
            print(-1)
            flag=False
            break
        cleaner[idx] +=tmp-1
    if flag:
        #각각 먼지 사이의 거리 구하기 
        DustToDust=[[0 for _ in range(len(dusts))] for _ in range(len(dusts))]
        for i in range(len(dusts)-1):
            visit=bfs(dusts[i][0],dusts[i][1])
            for j in range(i+1,len(dusts)):
                #다음 먼지 까지의 거리 저장
                DustToDust[i][j] =visit[dusts[j][0]][dusts[j][1]]-1
                DustToDust[j][i] = DustToDust[i][j]
        ans=sys.maxsize
        for p in permutations(range(len(dusts))):
            start=p[0]
            dist=cleaner[p[0]]
            for idx in range(1,len(p)):
                end=p[idx]
                dist+=DustToDust[start][end]
                #시작점 갱신
                start=end
            ans=min(ans,dist)
        print(ans)