(파이썬) 백준 4991번 : 로봇 청소기

최근 알고리즘 대회 등에 나갔을 때 어려운 문제를 알아보는것에 대한 중요성을 느꼈었다. 그래서 백준 문제별 등급표시를 꺼뒀더니... 이 문제가 걸렸다... 좋은건지 안좋은건지...

---

문제 

 

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

 

문제 이해

 

- w x h 의 격자판이 주어짐

- 로봇청소기가 가구를 피해 더러운 곳을 청소

- 더러운 칸을 모두 청소했을 때 최단거리는?  -> 외판원 순회 문제이다. 아마 이전에 풀었던 2098번과 비슷할 듯..

- 더러운 칸은 10개 이하 -> 비트마스킹을 DP 인덱스에 사용한다 (방문한 상황, 직전 방문한 위치)

 

코드 설명

 

- 일단 더러운 칸을 전부 모아두고 각각을 시작으로 bfs를 돌린다

- 각 칸에서 다른 칸으로 가는 거리를 딕셔너리로 저장해두자. 

   - 만약 bfs 돌렸을때 -1이 나왔다면? 어떻게서든 접근할 수 없는 칸이 나온 것 -> return -1로 끝낸다.

  -> dist_remove는 {0:{1:2,2:4,3:4,4:5,...},{},..} 이런 식으로 0에서 출발해 3으로 가는건 거리 4.

 

=> 더러운 칸의 사이 거리들을 전부 구할 수 있다. (dist_remove)

 

- 그 다음은 DP로 전부 방문했을때의 최단 거리를 구한다.

- dp [청소해야하는 칸의 수만큼 2의 제곱] [청소해야하는 칸의 수 <-직전 청소한곳] = 전부 INF

- 갱신해가면서 최종적으로 최단거리 구함.
dp[mask | (1 << v)][v] = min( dp[mask | (1 << v)][v], dp[mask][u] + dist_remove[u][v] )

 

import sys
from collections import deque
 
input = sys.stdin.readline
 
dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
 
 
def valid(x, y):
    return 0 <= x < h and 0 <= y < w
 
 
def bfs(start):
    dist = [[-1] * w for _ in range(h)]
    queue = deque([start])
    dist[start[0]][start[1]] = 0
 
    while queue:
        x, y = queue.popleft()
        for dx, dy in dir:
            xx, yy = x + dx, y + dy
            if valid(xx, yy) and G[xx][yy] != "x" and dist[xx][yy] == -1:
                dist[xx][yy] = dist[x][y] + 1
                queue.append((xx, yy))
 
    return dist
 
 
def solve(w, h):
    dirty_box = []
    start = None
 
    for i in range(h):
        for j in range(w):
            if G[i][j] == "*":
                dirty_box.append((i, j))
            elif G[i][j] == "o":
                start = (i, j)
 
    dirty_box.insert(0, start)
    remove_num = len(dirty_box)
    dist_remove = [[0] * remove_num for _ in range(remove_num)]
    for i in range(remove_num):
        sx, sy = dirty_box[i]
        short_paths = bfs((sx, sy))  # i 출발 최단거리들
        for j in range(remove_num):  # i와 j 사이의 거리들
            if i != j:
                tx, ty = dirty_box[j]
                if short_paths[tx][ty] == -1:
                    return -1
                dist_remove[i][j] = short_paths[tx][ty]
 
    # DP
    INF = float("inf")
    dp = [[INF] * remove_num for _ in range(1 << remove_num)]  # 비트마스킹
    dp[1][0] = 0 
   #dirty_box의 첫번째는 스타트위치. 0000...01. 첫번째 인덱스는 현재 상태. 두번재 인덱스는 그 전의 위치
 
    for mask in range(1 << remove_num):
        for u in range(remove_num):
            if mask & (1 << u):  # u 방문함
                for v in range(remove_num):
                    if not (mask & (1 << v)):  # v는 방문안함 -> u 후 v를 방문할때
                        dp[mask | (1 << v)][v] = min(
                            dp[mask | (1 << v)][v], dp[mask][u] + dist_remove[u][v]
                        )
 
    result = INF
    final_mask = (1 << remove_num) - 1
    for i in range(1, remove_num):
        result = min(result, dp[final_mask][i])
 
    return result if result != INF else -1
 
 
ans = []
while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    G = [list(input().strip()) for _ in range(h)]
 
    ans.append(str(solve(w, h)))
print("\n".join(ans))